Find Right Interval

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<pair<int,int>> starts(n);
        for (int i = 0; i < n; ++i) starts[i] = {intervals[i][0], i};
        sort(starts.begin(), starts.end());
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            auto it = lower_bound(starts.begin(), starts.end(), make_pair(intervals[i][1], INT_MIN));
            ans[i] = it == starts.end() ? -1 : it->second;
        }
        return ans;
    }
};

import "sort"

func findRightInterval(intervals [][]int) []int {
    n := len(intervals)
    starts := make([][2]int, n)
    for i, iv := range intervals {
        starts[i] = [2]int{iv[0], i}
    }
    sort.Slice(starts, func(i, j int) bool {
        return starts[i][0] < starts[j][0]
    })
    ans := make([]int, n)
    for i, iv := range intervals {
        target := iv[1]
        j := sort.Search(n, func(k int) bool {
            return starts[k][0] >= target
        })
        if j == n {
            ans[i] = -1
        } else {
            ans[i] = starts[j][1]
        }
    }
    return ans
}

from typing import List
from bisect import bisect_left

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
        keys = [p[0] for p in starts]
        ans = [0] * n
        for i, iv in enumerate(intervals):
            j = bisect_left(keys, iv[1])
            ans[i] = -1 if j == n else starts[j][1]
        return ans

function findRightInterval(intervals) {
    const n = intervals.length;
    const starts = intervals.map((iv, i) => [iv[0], i]);
    starts.sort((a, b) => a[0] - b[0]);
    const ans = new Array(n);
    for (let i = 0; i < n; i++) {
        const target = intervals[i][1];
        let lo = 0, hi = n;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (starts[m][0] < target) lo = m + 1;
            else hi = m;
        }
        ans[i] = lo === n ? -1 : starts[lo][1];
    }
    return ans;
}

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) -> Integer.compare(a[0], b[0]));
        int[] ans = 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;
            }
            ans[i] = lo == n ? -1 : starts[lo][1];
        }
        return ans;
    }
}

function findRightInterval(intervals: number[][]): number[] {
    const n = intervals.length;
    const starts: [number, number][] = intervals.map((iv, i) => [iv[0], i]);
    starts.sort((a, b) => a[0] - b[0]);
    const ans: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
        const target = intervals[i][1];
        let lo = 0, hi = n;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (starts[m][0] < target) lo = m + 1;
            else hi = m;
        }
        ans[i] = lo === n ? -1 : starts[lo][1];
    }
    return ans;
}