Solution: Find Right Interval

Statement

You are given an array of intervals where each interval is represented by a pair $[start_i, end_i]$. The $start_i$ values are unique, meaning no two intervals begin at the same time.

The task is to find the right interval for each interval in the list. The right interval for an interval $i$ is an interval $j$ such that $start_j >= end_i$ and $start_j$ is minimized (i.e., it is the smallest start time among all valid intervals that is greater than or equal to $end_i$). Note that $i$ may equal $j$.

Return an array of right interval indexes for each interval $i$. If no right interval exists for interval $i$, then put $-1$ at index $i$.

Constraints:

• $1 \leq$ intervals.length $\leq 1000$

• intervals[i].length $== 2$

• $-10^6 \leq start_i \leq end_i \leq 10^6$

• 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:

1. Initializing a result array with -1 for each interval, representing cases where no right interval is found.

2. Initialize two min heaps:

   1. A startHeap stores tuples of (start, index), where start is the interval's start time and index is its original position in the input list.

   2. An endHeap stores tuples of (end, index), where end is the interval's end time and index is its original position.

3. Iterate over the intervals, pushing start times into startHeap and end times into endHeap.

4. For each interval, pop the smallest end time from endHeap and remove any start times in startHeap that are smaller than the current end time. This ensures that we only consider start times that could be valid right intervals.

5. 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 the result array with the corresponding index of this right interval.

6. 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: