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


  • 0
    R

    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 compand 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;
            
        }
    };
    

Log in to reply
 

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