C++ Binary Search solution with comment


  • 0
    H
    typedef pair<int, int> pi; 
    
    class Solution {
    public:
        vector<int> findRightInterval(vector<Interval>& intervals) {
            vector<pi> s;
            vector<int> res;
            int n = intervals.size();
            for (auto i = 0; i < n; ++i) {
                pi p;
                p.first = intervals[i].start;
                p.second = i;
                s.push_back(p);
            }
            sort(s.begin(), s.end());
            for (auto in : intervals) {
                // Do binary search
                int l = 0;
                int hi = s.size() - 1;
                while (l < hi) {
                    int mid = (l + hi) / 2;
                    if (s[mid].first < in.end) {
                        l = mid + 1; // move left until meet upper bound
                    } else {
                        hi = mid; // set upper bound to the min start point that bigger than end point or meet the lower bound
                    }
                }
                if (s[l].first < in.end)
                    res.push_back(-1);
                else 
                    res.push_back(s[l].second);
            }
            return res;
        }
    };
    

Log in to reply
 

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