Leetcode 436 Solution

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int FindFirstNotLessThan(const vector<pair<int, int>>& a, int target)
    {
        int l = 0;
        int r = a.size() - 1;

        while (l <= r)
        {
            int m = (l + r) / 2;

            if (a[m].first >= target)
                r = m - 1;
            else
                l = m + 1;
        }

        if (l < a.size())
            return a[l].second;
        else
            return -1;
    }

    vector<int> findRightInterval(vector<Interval>& intervals) {
        vector<pair<int, int>> a(intervals.size());
        vector<int> res(intervals.size());

        for (int i = 0; i < intervals.size(); i++)
        {
            a[i].first = intervals[i].start;
            a[i].second = i;
        }

        sort(a.begin(), a.end(),  [] (const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.first < rhs.first;});

        for (int i = 0; i < intervals.size(); i++)
        {
            res[i] = FindFirstNotLessThan(a, intervals[i].end);
        }

        return res;
    }
};