Solution: Find Right Interval
Let's solve the Find Right Interval problem using the Two Heaps pattern.
We'll cover the following
Statement
You are given an array of intervals
where each interval is represented by a pair
The task is to find the right interval for each interval in the list. The right interval for an intervalÂ
Return an array of right interval indexes for each intervalÂ
Constraints:
intervals.length
intervals[i].length
The start times are guaranteed to be unique.
Solution
We use two heaps to find the right interval for each given interval. One heap keeps track of the intervals' end times, allowing us to process them in the order they finish. The other heap stores the start times, helping us quickly identify the smallest valid start time that can serve as the right interval. By processing intervals based on their end times, we remove all start times from the start heap that are smaller than the current end time. This way, we ensure that any remaining start times in the heap are candidates for the right interval. Once we have removed all smaller elements from the start min heap, if the heap is not empty, the top element (smallest valid start time) represents the right interval. This approach optimizes the search process, avoiding unnecessary comparisons and reducing the overall complexity.
The steps of the algorithm are given below:
Initializing a
result
array with-1
for each interval, representing cases where no right interval is found.Initialize two min heaps:
A
startHeap
stores tuples of (start, index), wherestart
is the interval's start time andindex
is its original position in the input list.An
endHeap
stores tuples of (end, index), whereend
is the interval's end time andindex
is its original position.
Iterate over the intervals, pushing start times into
startHeap
and end times intoendHeap
.For each interval, pop the smallest end time from
endHeap
and remove any start times instartHeap
that are smaller than the current end time. This ensures that we only consider start times that could be valid right intervals.After the invalid start times are removed, if
startHeap
is not empty, the top element (smallest valid start time) represents the right interval. We then update theresult
array with the corresponding index of this right interval.Once all intervals are processed, the
result
array contains the indexes of the smallest right intervals or-1
if no valid interval exists.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.