Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 1: Next Interval

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

An example showing that the next interval can be at any index would be helpful

A

Anonymous

· 2 years ago

from heapq import *

class Solution:
  def findNextInterval(self, intervals):
    
    e_min_heap = []
    s_min_heap = []

    for i in range(len(intervals)):
      s_min_heap.append((intervals[i].start, i))
      e_min_heap.append((intervals[i].end, i))

    heapify(s_min_heap)
    heapify(e_min_heap)  

    result = [-1 for _ in range(len(intervals))]

    while e_min_heap:
      end, end_index = heappop(e_min_heap)

      while s_min_heap:
        start, start_index = heappop(s_min_heap)
        if start_index > end_index and start >= end:
          result[end_index] = start_index
          break
      
    return result
A

Anonymous

· 3 years ago

I think using max heaps is more confusing rather than using min heap, and also, min heaps don't require pushing again any of the intervals

from heapq import heappop, heappush


#class Interval:
#  def __init__(self, start, end):
#    self.start = start
#    self.end = end


class Solution:
  def findNextInterval(self, intervals):
    n = len(intervals)
    result = [-1] * n
    end_heap = []
    begin_heap = []

    for i in range(n):
      b, e = intervals[i].start, intervals[i].end

      heappush(end_heap, (e, i))
      heappush(begin_heap, (b, i))

    while end_heap:
      e, i = heappop(end_heap)

      while begin_heap and begin_heap[0][0] < e:
          heappop(begin_heap)

      if begin_heap and begin_heap[0][0] >= e:
          result[i] = begin_heap[0][1]
    
   
A

Anonymous

· 4 years ago

I think the article misses an obvious discussion about TreeMap. The challange can be solved efficiently with a TreeMap because of it TreeMap#ceilingEntry method that works O(log N) time. Every interval is uniquely identified by its starting point. Filing in the map with intervals and then querying it for a next entry seems like an obvious choice for me.

It beat 80% of solutions on leetcode: https://pastebin.com/r1bc0EwT Image

Show 4 replies
A

Anonymous

· 4 years ago

I think the implementation given is confusing, and only a single min heap is needed with no time complexity additions. A much simpler implementation would:

  1. put all intervals into a min-heap sorted by start time. In this same loop, keep track of the minimum intervalEnd

  2. Pop from the min heap while heapTop().st art < intervalEnd

  3. For every interval...

3a) get the interval end of the top of the heap O(1) * O(N) 3b) pop off the min heap while heapTop().st art < intervalEnd 3c) Add interval or -1 to solution

def solve(intervals): solution = []

construct heap sorted by start time

minHeap = [] intervalEnd = math.inf for i in range(len(intervals)): [s, e] = intervals[i] heappush(minHeap, H(s, e, i)) intervalEnd = min(intervalEnd, e)

Clean up minHeap so that minHeap[0].start >= i

Show 2 replies
A

Anonymous

· 4 years ago

Instead of using max heaps, using min heaps would be more straightforward. When using max heaps, you may have to pop from the start heap multiple times to find the closest start, then add the last interval back in. With a minStartHeap and minEndHeap, the first cur_start >= cur_end and s_i != s_e is guaranteed to be the interval with the closest start value. Upon fulfilling this condition, pop from minEndHeap, and the next cur_end is guaranteed to be >= cur_start.

Show 1 reply
A

Anonymous

· 4 years ago

I think the Java solution has an error. For the two heap insertion for-loop, the index 'i' is offered into the heap, instead of the actual interval[i]. This would mean other parts of the code need refactoring too, as it leverages this index-based heap.

Maybe storing the index in the Interval class might be better (as a member variable, e.g. Interval.index).

Reading Progress

0%

Vote for new content