Find Right Interval

medium array binary search sorting

Problem

For each interval i, find the index j of the interval with the smallest start ≥ end_i. If no such interval exists, return -1 for that position.

Inputintervals = [[3,4], [2,3], [1,2]]

Output[-1, 0, 1]

Interval[0]=[3,4] has no right interval; [2,3] points to index 0 (start 3 ≥ end 3); [1,2] points to index 1 (start 2 ≥ end 2).

intervals (e.g. 3,4;2,3;1,2)

from bisect import bisect_left

def find_right_interval(intervals):
    starts = sorted([(s, i) for i, (s, _) in enumerate(intervals)])
    keys = [s for s, _ in starts]
    res = []
    for s, e in intervals:
        j = bisect_left(keys, e)
        res.append(starts[j][1] if j < len(starts) else -1)
    return res

function findRightInterval(intervals) {
  const starts = intervals.map((iv, i) => [iv[0], i]).sort((a, b) => a[0] - b[0]);
  const keys = starts.map(p => p[0]);
  const lower = (arr, target) => {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (arr[m] < target) lo = m + 1; else hi = m;
    }
    return lo;
  };
  return intervals.map(([s, e]) => {
    const j = lower(keys, e);
    return j < starts.length ? starts[j][1] : -1;
  });
}

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] starts = new int[n][2];
        for (int i = 0; i < n; i++) { starts[i][0] = intervals[i][0]; starts[i][1] = i; }
        Arrays.sort(starts, (a, b) -> a[0] - b[0]);
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int target = intervals[i][1];
            int lo = 0, hi = n;
            while (lo < hi) {
                int m = (lo + hi) >>> 1;
                if (starts[m][0] < target) lo = m + 1; else hi = m;
            }
            res[i] = lo < n ? starts[lo][1] : -1;
        }
        return res;
    }
}

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++) {
        auto it = lower_bound(starts.begin(), starts.end(), make_pair(intervals[i][1], INT_MIN));
        res[i] = it == starts.end() ? -1 : it->second;
    }
    return res;
}

Explanation

For each interval we want the one whose start is the smallest value still at least as big as our end. Searching all intervals every time is slow, so we sort the starts once and use binary search.

We build pairs (start, originalIndex) and sort them by start. Keeping the original index is essential, because the answer must point back to where the interval was before sorting.

For an interval ending at e, a bisect_left / lower-bound on the sorted starts finds the first start that is >= e. If such a position j exists we return starts[j]'s original index; if the search falls off the end, no right interval exists and we return -1.

Example: [[3,4],[2,3],[1,2]] sorts starts to [(1,2),(2,1),(3,0)]. For [3,4] nothing starts at >= 4, so -1; [2,3] finds start 3 at index 0; [1,2] finds start 2 at index 1, giving [-1, 0, 1].

Sorting plus a binary search per interval keeps the whole thing efficient even with many intervals.

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