Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 1: Next Interval (hard)

Problem Statement

Given an array of intervals, find the next interval of each interval. In a list of intervals, for an interval ‘i’ its next interval ‘j’ will have the smallest ‘start’ greater than or equal to the ‘end’ of ‘i’.

Write a function to return an array containing indices of the next interval of each input interval. If there is no next interval of a given interval, return -1. It is given that none of the intervals have the same start point.

Example 1:

Input: Intervals [[2,3], [3,4], [5,6]]  
Output: [1, 2, -1]

.....

.....

.....

Like the course? Get enrolled and start learning!
Renat Zamaletdinov

Renat Zamaletdinov

· 2 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]
    
   
W

Will

· 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).

M

Michelle Cheng

· 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
M

Mikhail Putilov

· 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
P

Pete Stenger

· 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
Mohammed Dh Abbas

Mohammed Dh Abbas

· 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
Show 1 reply
P

Pete Stenger

· 2 years ago

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

Parikshit Murria

Parikshit Murria

· a year ago

import java.util.*;

/*class Interval {
  int start = 0;
  int end = 0;

  Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
}*/

class Solution {

  public static int[] findNextInterval(Interval[] intervals) {

    Queue<Integer> minEndHeap = new PriorityQueue<>((i,j) -> intervals[i].end - intervals[j].end);
    Queue<Integer> minStartHeap = new PriorityQueue<>((i,j) -> intervals[i].start - intervals[j].start);

    int n = intervals.length;
    int[] result = new int[n];

    for (int i=0; i<n; i++) {
      minEndHeap.offer(i);
      minStartHeap.offer(i);
    }

     while(!minEndHeap.isEmpty()) {
     
      int endIdx = minEndHeap.poll();

      int endTime = intervals[endIdx].end;
      result[endIdx] = -1;

      while(!minStartHeap.isEmpty