# c++ solution, binary search using lower_bound, beat 88%

• The basic idea is, bound the position of element in Intervals vector with Interval objects (`make_pair`), and sort the new vector of type `pair<int,Interval>` according to the 'start' property.
loop through all the element in the sorted vector, for each element, find the first element after the element in the vector and has 'start' property greater than the 'end' of the element, take the advantage of the position value we stored, get the position information.
two template function from <algorithm> is used, `sort` with lambda expression `comp`and `lower_bound` with lambda expression `newcompare`

``````
class Solution {
public:
vector<int> findRightInterval(vector<Interval>& intervals) {
vector<pair<int,Interval>> sorted_intervals;

for(int i=0;i<intervals.size();++i)
{
sorted_intervals.push_back(make_pair(i,intervals[i]));
}

auto comp=[](pair<int,Interval> &a,pair<int,Interval> &b)->
bool{return a.second.start<b.second.start;};

sort(sorted_intervals.begin(),sorted_intervals.end(),comp);

vector<int> res(intervals.size());//construct the result vector first;

auto newcompare=[](pair<int,Interval> &c,const int val)->
bool{return c.second.start<val;};

for(int i=0;i<intervals.size();++i)
{

auto current_it=sorted_intervals.begin()+i;
auto res_it=lower_bound(current_it,sorted_intervals.end(),(*current_it).second.end,newcompare);
if(res_it==sorted_intervals.end())
//if we don't find the required interval
res[(*current_it).first]=-1;
else
res[(*current_it).first]=(*res_it).first;
}
return res;

}
};
``````

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