436. Find Right Interval

1. Description

You are given an array of intervals, where intervals[i] = [$start_i$, $end_i$] and each $start_i$ is unique.
The right interval for an interval i is an interval j such that $start_i$ >= $end_i$ and $start_i$ 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.

2. Example

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.

3. Constraints

• 1 <= intervals.length <= $2 * 10^4$
• intervals[i].length == 2
• -10$^{6}$ <= $start_i$ <= $end_i$ <= 10$^{6}$

4. Solutions

Binary Search & Sorting

n = intervals.size()
Time complexity: O(nlogn)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>> &intervals) {
        vector<int> left_borders(intervals.size());
        unordered_map<int, int> left_border_index;
        for (int i = 0; i < intervals.size(); ++i) {
            left_borders[i] = intervals[i][0];
            left_border_index[left_borders[i]] = i;
        }
        sort(left_borders.begin(), left_borders.end());

        vector<int> result(intervals.size(), -1);
        for (int i = 0; i < intervals.size(); ++i) {
            int right_border = intervals[i][1];
            for (int left = 0, right = left_borders.size(); left < right;) {
                int mid = (left + right) / 2;

                left_borders[mid] >= right_border
                    ? (right = mid, result[i] = left_border_index[left_borders[mid]])
                    : left = mid + 1;
            }
        }

        return result;
    }
};