LeetCode435 -- 预定会议问题

0. ref

参考自

1. 题目描述

预定会议问题：给定我们一堆区间，区间不能重叠（\([1,2]\) 和 \([2,3]\) 的 \(2\) 不算重叠），求最多能保留多少个区间？

做法：贪心，按【右端点】排序。
为什么要按照右端点排序？反证，如果按照左端点排序，看下面的例子：

|_________|                  区间a
  |___|                      区间b       
       |__|                  区间c   
            |______|         区间d   

如果按照左端点升序的话，那么答案就是 \(2\) 了，但显然，答案应该是 \(3\)。
我们把区间的左右端点比作会议的开始和结束时间，一句话：开始早的会议不一定结束早！
如果我们按照右端点排序，那么一定能留给后面的会议更长的时间。

本题其实还有另外一种做法：\(LCS\)，只不过是一个二维 \(LCS\) 问题，而且由于区间之间不是严格大于的原因，为我们避免了不必要的麻烦！
参见 my blog here，我们可以直接 sort，不需要制定自定义 cmp。
只不过，第一种做法是：\(O(Nlog^{N} + N)\)，而 \(LCS\) 是 \(O(Nlog^{N} + Nlog^{N})\)，常数大一点罢了。

2. 思路

3. 代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [&](auto &x, auto &y){
            if(x[1] == y[1])    return x[0] < y[0];
            return x[1] < y[1];
        });
        int res = 0;
        int right = -2e9;
        for(auto &x : intervals) {
            if(x[0] >= right) {
                right = x[1];
                res ++ ;
            }
        }
        return intervals.size() - res;
    }
};