436. Find Right Interval

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 >= 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.

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& I) {
        int n = I.size();
        map<int, int> mp;
        for(int i = 0; i < n; i++) {
            mp[I[i][0]] = i;
        }
        vector<int> res(n, -1);
        for(int i = 0; i < n; i++) {
            auto it = mp.lower_bound(I[i][1]);
            res[i] = it == end(mp) ? -1 : it->second;
        }
        
        return res;
    }
};