Leetcode 435 Non-overlapping Intervals
https://leetcode.com/problems/non-overlapping-intervals/

Interval的題目一定要排序，跑不了。這種題的做法都是排序，然后把起點設(shè)為interval[0], 然后從interval[1] 開始循環(huán)。同時，按照起點排序，與按照終點排序是一樣的。

這道題，排序方法按照start排就可以了。但難點是，排序后在掃interval時，如果該點的end小，就要以該點的end來算。重合時，永遠(yuǎn)刪除區(qū)間長的。([1, 10], [2, 8], [9, 10], 這個區(qū)間，要刪除[1,10], 這個得在for loop里面做，排序時無法解決)。

int eraseOverlapIntervals(vector<Interval>& intervals) {
        if(intervals.empty()) return 0;
        auto comp = [](const Interval &v1, const Interval &v2){
            return v1.start < v2.start;
        };
        sort(intervals.begin(), intervals.end(), comp);
        int cnt = 0, end = intervals[0].end;
        for(int i=1; i<intervals.size(); i++){
            if(end > intervals[i].start){
                cnt++;
                if(intervals[i].end < end) end = intervals[i].end; //!!!
            }
            else end = intervals[i].end;
        }
        return cnt;
        
    }

這道題的一個衍生題是: “給定一堆區(qū)間，找最多多少個non-overlapping的區(qū)間”. 要點是按照end排序，而不是start。然后掃的時候，如果重復(fù)，要更新count.

int end = intervals[0].end;
int count = 1;        
for (int i = 1; i < intervals.length; i++) {
    if (intervals[i].start >= end) {
        end = intervals[i].end;
        count++;
    }
}

Leetcode 452: Minimum Number of Arrows to Burst Balloons
https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

這道題也差不多，這種題的做法都是排序，然后把起點設(shè)為interval[0], 然后從interval[1] 開始循環(huán)。

 int findMinArrowShots(vector<pair<int, int>>& points) {
        if(points.empty()) return 0;
        sort(points.begin(), points.end());
        int start = points[0].second, cnt = 1;
        for(int i=1; i<points.size(); i++){
            if(start >= points[i].first){
                start = min(start, points[i].second);   
            }else{
                cnt++;
                start = points[i].second;
            }
        }
        return cnt;
    }

436 Find Right Interval
https://leetcode.com/problems/find-right-interval/

也是對于起點排序，然后對于每一個end point，做binary search

int search(int target, vector<pair<int, int>> &current){
        int left = 0, right = current.size()-1;
        while(left < right){
            int mid = left + (right-left)/2;
            if(current[mid].first < target) left = mid+1;
            else right = mid;
        }
        return current[left].first >= target ? current[left].second : -1;
    }
    
    vector<int> findRightInterval(vector<Interval>& intervals) {
        if(intervals.empty()) return vector<int>();
        vector<int> ret(intervals.size(), 0);
        vector<pair<int, int>> current;
        for(int i=0; i<intervals.size(); i++){
            current.push_back({intervals[i].start, i});
        }
        auto comp = [](const pair<int, int> &p1, const pair<int, int> &p2){
            return p1.first < p2.first;
        };
        sort(current.begin(), current.end(), comp);
        for(int i=0; i<intervals.size(); i++){
            int cur = search(intervals[i].end, current);
            ret[i] = cur;
        }
        return ret;
    }