0. ref

參考自

1. 題目描述

預定會議問題：給定我們一堆區間，區間不能重疊（$[1,2]$ 和 $[2,3]$ 的 $2$ 不算重疊），求最多能保留多少個區間？

做法：貪心，按**【右端點】**排序。
為什么要按照右端點排序？反證，如果按照左端點排序，看下面的例子：

|_________|                  區間a|___|                      區間b       |__|                  區間c   |______|         區間d   

如果按照左端點升序的話，那么答案就是 $2$ 了，但顯然，答案應該是 $3$。
我們把區間的左右端點比作會議的開始和結束時間，一句話：開始早的會議不一定結束早！
如果我們按照右端點排序，那么一定能留給后面的會議更長的時間。

本題其實還有另外一種做法：$LCS$，只不過是一個二維 $LCS$ 問題，而且由于區間之間不是嚴格大于的原因，為我們避免了不必要的麻煩！
參見 my blog here，我們可以直接 sort，不需要制定自定義 cmp。
只不過，第一種做法是：$O(Nlo{g}^N+N)$，而 $LCS$ 是 $O(Nlo{g}^N+Nlo{g}^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;}
};