educative.io

A slightly simpler and a bit more optimized solution

Courses
,
#1

Why not use min heaps instead of max heaps? Its easier to understand. Or maybe I’m missing something?

Also, you can stop looping when there are no more candidates for a next interval.

Of course heaps don’t have a major advantage over sorted lists except perhaps making the code a tiny bit simpler.

from heapq import heappush, heappop

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

def find_next_interval(intervals):
  by_start_time = []
  by_end_time = []
  result = [-1]*len(intervals)

  for idx, interval in enumerate(intervals):
    heappush(by_start_time, (interval.start, idx))
    heappush(by_end_time,   (interval.end,   idx))

  while by_end_time and by_start_time:
    end_time, idx = heappop(by_end_time)
    while by_start_time and by_start_time[0][0] < end_time:
      heappop(by_start_time)
    if by_start_time:
      result[idx] = by_start_time[0][1]

  return result
7 Likes
#2

Yes, I think, min heaps are the right answer here. Max heaps might give a wrong answer.

#3

I also think it can work with min heaps. It would be great if authors could clarify the usage of max heaps here.
I used a slightly different loop:

while endHeap and startHeap:
  minEnd, idxEnd = heappop(endHeap)
  minStart, idxStart = heappop(startHeap)

  if idxEnd == idxStart or minEnd > minStart:
    heappush(endHeap, (minEnd, idxEnd))
    continue

  result[idxEnd] = idxStart
#5

I think min heap is also a right solution here. We store the end time and start time in heaps from smallest to biggest. While both heaps are not empty, we get the smallest end time and we use that to find the next interval in the start heap. If the current smallest start time is less than the current end time, that means the current interval in start heap cannot be the next interval, so pop it and keep searching and if no such interval exists, do nothing since we initialized the result list of -1

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 1 - Grokking the Coding Interview: Patterns for Coding Questions