{x}
blog image

Find Right Interval

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j.

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

 

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

 

Constraints:

  • 1 <= intervals.length <= 2 * 104
  • intervals[i].length == 2
  • -106 <= starti <= endi <= 106
  • The start point of each interval is unique.

Solution Explanation: Find Right Interval

This problem asks to find the right interval for each interval in a given array of intervals. A right interval for interval i is an interval j where start<sub>j</sub> >= end<sub>i</sub> and start<sub>j</sub> is minimized (the smallest possible start time that satisfies the condition). If no such interval exists, we use -1.

The most efficient approach leverages sorting and binary search.

Algorithm:

  1. Create an auxiliary array: We create an array arr where each element is a pair (start<sub>i</sub>, index<sub>i</sub>). This array stores the start time of each interval and its original index in the input array.

  2. Sort the auxiliary array: We sort arr in ascending order based on the start times (start<sub>i</sub>). This allows for efficient binary search later.

  3. Iterate through intervals: We iterate through the original intervals array. For each interval [start<sub>i</sub>, end<sub>i</sub>], we perform the following steps:

  4. Binary search: We perform a binary search on the sorted arr to find the smallest start time start<sub>j</sub> such that start<sub>j</sub> >= end<sub>i</sub>. The lower_bound (or equivalent) function in the chosen language helps find this efficiently.

  5. Store the result: If a right interval is found (the binary search returns a valid index), we store the original index of that interval (index<sub>j</sub>) in the ans array at the corresponding position (original index i). Otherwise, we store -1.

  6. Return the answer: Finally, we return the ans array containing the indices of the right intervals for each interval.

Time Complexity: O(n log n) - dominated by sorting the auxiliary array and performing n binary searches. Each binary search takes O(log n) time.

Space Complexity: O(n) - to store the auxiliary array arr and the result array ans.

Code Examples (Python, Java, C++, Go, TypeScript):

The code examples provided in the original response demonstrate the algorithm in several languages. Each example follows the steps outlined above: creating an auxiliary array, sorting it, iterating through the input intervals, performing binary search, and storing results. The specific functions for binary search (like bisect_left in Python, lower_bound in C++, or sort.Search in Go) may differ across languages, but the underlying logic remains the same. The Java example shows a custom binary search implementation (search function) for clarity.

Example Walkthrough (Python):

Let's consider the input intervals = [[1,4],[2,3],[3,4]].

  1. arr will be [(1, 0), (2, 1), (3, 2)] after creation and sorting.

  2. Iterating through intervals:

    • For [1, 4], binary search in arr for a start time >= 4 finds no match, so ans[0] = -1.
    • For [2, 3], binary search finds (3, 2), so ans[1] = 2.
    • For [3, 4], binary search finds no match, so ans[2] = -1.

  3. The final ans will be [-1, 2, -1].

The other language examples follow this same process, adapting the syntax and specific functions as needed for each language. The time and space complexities remain consistent across implementations.