C++ O(nlogn) solution in 14 lines


  • 0
    P
    vector<int> findRightInterval(vector<Interval>& intervals) {
        vector< pair<Interval, int> > intervalIndex;
        for (int i = 0; i < intervals.size(); i++) intervalIndex.push_back(make_pair(intervals[i], i));
        sort(intervalIndex.begin(), intervalIndex.end(), [](pair<Interval, int> a, pair<Interval, int> b){return a.first.start < b.first.start;});
        vector<int> res(intervals.size(), -1);
        for (auto ii : intervalIndex) {
            int left = 0, right = intervals.size() - 1, mid;
            while (right - left > 0) {
                mid = (left + right) / 2;
                if (intervalIndex[mid].first.start - ii.first.end >= 0) right = mid;
                else left = mid + 1;
            }
            if (intervalIndex[left].first.start - ii.first.end >= 0) res[ii.second] = intervalIndex[left].second;
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.