Interval Problem 小结 (Leetcode)

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

Interval的题目一定要排序，跑不了。这种题的做法都是排序，然后把起点设为interval[0], 然后从interval[1] 开始循环。同时，按照起点排序，与按照终点排序是一样的。

这道题，排序方法按照start排就可以了。但难点是，排序后在扫interval时，如果该点的end小，就要以该点的end来算。重合时，永远删除区间长的。([1, 10], [2, 8], [9, 10], 这个区间，要删除[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;
        
    }

这道题的一个衍生题是: “给定一堆区间，找最多多少个non-overlapping的区间”. 要点是按照end排序，而不是start。然后扫的时候，如果重复，要更新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/

这道题也差不多，这种题的做法都是排序，然后把起点设为interval[0], 然后从interval[1] 开始循环。

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