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 &gt;= 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.

&nbsp;
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 &gt;= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is &gt;= 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 &gt;= end1 = 3.


&nbsp;
Constraints:


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


class Solution:
    def findRightInterval(self, A: List[List[int]]) -> List[int]:
        n = len(A)
        ans = [-1] * n

        for i in range(n):
            A[i].append(i)

        A.sort()
        heap = []

        for i in range(n):
            if A[i][0] == A[i][1]:
                ans[A[i][2]] = A[i][2]
            else:
                while heap and heap[0][0] <= A[i][0]:
                    ans[heapq.heappop(heap)[1]] = A[i][2]
                
                heapq.heappush(heap, [A[i][1], A[i][2]])

        return ans
/*
- Time: O(N*log(N))
Loop through the array with n elements and run binary search with log(N) time for each of them.

- Space: O(N)
Used a hashmap map of size N to store the original indeces of intervals
 */
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[] res = new int[n];
        Map<int[], Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(intervals[i], i);
        }

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            int[] interval = binarySearch(intervals, intervals[i][1], i);
            res[map.get(intervals[i])] = interval == null ? -1 : map.get(interval);
        }
        
        return res;
    }

    private int[] binarySearch(int[][] intervals, int target, int start) {
        int l = start, r = intervals.length - 1;
        
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (intervals[m][0] >= target) {
                // keep moving the right boundary to the left to get the first
                // element bigger than target
                r = m - 1;
            } else {
                // if the element we get is bigger than the target, we move the 
                // left boundary to look at right part of the array
                l = m + 1;
            }
        }
        return l == intervals.length ? null : intervals[l];
    }
}
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {

        map<int, int> mp;
        int n = intervals.size();

        for(int i = 0; i < n; i++)
            mp[intervals[i][0]] = i;

        vector<int> ans;
        for(auto &i : intervals)
        {
            auto it = mp.lower_bound(i[1]);
            ans.push_back(it == mp.end() ? -1 : it->second);
        }

        return ans;
    }
};
var findRightInterval = function(intervals) {
    const data = intervals
        .map((interval, i) => ({ interval, i }))
        .sort((a, b) => a.interval[0] - b.interval[0]);

    const res = Array(intervals.length).fill(-1);

    for (let pos = 0; pos < data.length; pos++) {
        let left = pos;
        let right = data.length - 1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);

            if (data[pos].interval[1] <= data[mid].interval[0]) {
                right = mid - 1;
            } else {
                left = mid + 1;                    
            }
        }

        if (left < data.length) {
            res[data[pos].i] = data[left].i;
        }
    }
    
    return res;
};
Find Right Interval