C++ sort and binary search solution, highly straightforward


  • 0

    The following is not the fastest solution but is very intuitive. I use a hashtable to store the ordering information of the input before I sort it. Then I perform binary search and store the result index with the help of the hashtable.

    vector<int> findRightInterval(vector<Interval>& intervals) {
        unordered_map<int, int> startToIdx;
        for (int i = 0; i < intervals.size(); i++) {
        	startToIdx[intervals[i].start] = i;
        }
        auto cmp = [] (const Interval& interval1, const Interval& interval2) {
        	return interval1.start < interval2.start;
        };
        sort(intervals.begin(), intervals.end(), cmp);
        vector<int> res(intervals.size());
        for (int i = 0; i < res.size(); i++) {
        	int resIdx = startToIdx[intervals[i].start];
        	Interval lowerBoundInterval(intervals[i].end, intervals[i].end+1);
        	auto it = lower_bound(intervals.begin(), intervals.end(), lowerBoundInterval, cmp);
        	res[resIdx] = it == intervals.end() ? -1 : startToIdx[it->start];
        }
        return res;
    }
    

Log in to reply
 

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