原本想說用greedy的思路去解題，如果intervals[i][0]小於前一個區間的終點就加一，但反例[[1,4],[2,5],[4,6]]證明是行不通。後來才發現我忽略了一個重要的點，並非要小於前一個區間的終點，而是要小於前一個未被移除區間的終點。
先說個前提，這問題和 intervals scheduling problem 是等價。原本 leetcode 是移除最少區間數量使得該集合L內的所有區間都沒有重疊，其等價於最大化L的數量。
做法其實很簡單，只要按區間的終點升序去排後，如果區間i的起點小於上一個未被移除區間i*的終點則不取i，否則更新i*=i。
bool sortEnd(const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
}
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), sortEnd);
int num = 0;
auto prev = intervals[0];
for(size_t i=1; i<intervals.size(); i++){
if(intervals[i][0] < prev[1]){
num++;
}
else
prev = intervals[i];
}
return num;
}
};Time complexity: O(n*logn)
Space complexity: O(1)
關於 intervals scheduling problem 的 greedy algorithm 可行性證明可以參考這篇和MIT的線上課程，下面簡要說明一下證明並不是很嚴謹的定義。
假設OPT是最佳解的集合且|OPT|=m，而ALG是 greedy 找出來的結果且|ALG|=k，且兩個集合都已經照終點由小到大排序。若L’不是最佳則表示OPT存在一個區間j_{k+1}使得m>k，所以若符合以下特性，代表說greedy會把j_{k+1}加到ALG裡面，否則j_{k+1}這區間是不存在，若不存在則與原本假設m>k矛盾。
第一個式子非常的直觀，因為OPT的順序是照終點且j_k與j_{k+1}是不重疊的，而第二個式子我們只要可以證明 f(i_k) ≤ f(j_k) 就可以，下面用歸納法去證明。
當 r = 1時必然成立，假設r=k-1時成立，則r=k時，所以可以得出下式
前面兩個是因為假設成立，後面兩個是因為第k個的終點必然在k-1的起點後(含)，所以可以知道區間j_k的起點會在i_{k-1}的終點之後(含)，根據演算法的步驟，j_k必然會被加到ALG裡面，所以可以得出結論
在帶回原本m>k的假設證明中，可以發現若j_{k+1}存在，演算法會加進ALG裡面，但這樣就會與原本的假設矛盾，故證明m=k。