Simple C++ binary search solution.


  • 0
    J

    '''

        vector<int> findRightInterval(vector<Interval>& intervals) {
        vector<pair<int, int>> starts;//start,idx
        for (int i = 0; i < intervals.size();i++)
        {
            starts.push_back(make_pair(intervals[i].start, i));
        }
        
        sort(starts.begin(), starts.end());
        
        vector<int> ret;
        for (int i = 0; i < intervals.size(); i++)
        {
            int pos = lower_bound(starts.begin(), starts.end(), make_pair(intervals[i].end, 0)) - starts.begin();
            if (pos == starts.size()) 
            {
                ret.push_back(-1);
            }
            else
            {
                ret.push_back(starts[pos].second);
            }
            
        }
        
        return ret;
    }
    

    '''


Log in to reply
 

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