Find Right Interval

Problem Statement

For each interval [start_i, end_i], the "right interval" is the one with the smallest start_j >= end_i. Return an array of the indices of these right intervals, or -1 where none exists.

Example

Input:  intervals = [[3,4],[2,3],[1,2]]
Output: [-1, 0, 1]

Approach

Collect (start, originalIndex) and sort by start. For each interval’s end, binary-search (lower bound) the smallest start >= end and record that interval’s original index, or -1 if none.

Complexity

• Time: O(n log n)
• Space: O(n)

Solution Code

Python

import bisect
def findRightInterval(intervals):
    starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
    res = []
    for iv in intervals:
        pos = bisect.bisect_left(starts, (iv[1], -1))
        res.append(starts[pos][1] if pos < len(starts) else -1)
    return res

Java

int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    int[][] starts = new int[n][2];
    for (int i = 0; i < n; i++) starts[i] = new int[]{intervals[i][0], i};
    Arrays.sort(starts, (p, q) -> p[0] - q[0]);
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        int end = intervals[i][1], lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (starts[mid][0] < end) lo = mid + 1;
            else hi = mid;
        }
        res[i] = lo < n ? starts[lo][1] : -1;
    }
    return res;
}

C++

vector<int> findRightInterval(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<pair<int,int>> starts;
    for (int i = 0; i < n; i++) starts.push_back({intervals[i][0], i});
    sort(starts.begin(), starts.end());
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        int end = intervals[i][1], lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (starts[mid].first < end) lo = mid + 1;
            else hi = mid;
        }
        res[i] = lo < n ? starts[lo].second : -1;
    }
    return res;
}

Key Takeaways

• Sort starts together with their original indices so you can report them.
• The query is a lower bound: first start >= end.
• Reference: LeetCode 436 (Find Right Interval).