436. Find Right Interval

简单题，主要是题意的理解，先对start做一次排序，然后寻找每一个end在start数组中的位置，找到比他大的第一个数字所在的位置。

/** * 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: static bool cmp(pair<int,int>&a,pair<int,int>& b) { if(a.first<b.first) return true; else return false; } int findBigOrEqual(int num,vector<pair<int,int>>& starts) { int left=0; int right=starts.size()-1; if(num>starts[right].first) return -1; if(num<starts[left].first) return 0; while(left<right) { int mid=left+(right-left)/2; if(starts[mid].first<num) left=mid+1; else if(starts[mid].first>num) right=mid; else return starts[mid].second; } return starts[left].second; } vector<int> findRightInterval(vector<Interval>& intervals) { vector<pair<int,int>> starts; for(int i=0;i<intervals.size();i++) { pair<int,int> temp(intervals[i].start,i); starts.push_back(temp); } sort(starts.begin(),starts.end(),cmp);//[start,index] vector<int> result; for(int i=0;i<intervals.size();i++) { int num=intervals[i].end; result.push_back(findBigOrEqual(num,starts)); } return result; } };