[LeetCode]Non-overlapping Intervals

这道题等价于找到尽可能多的non-overlapping intervals，就是最少的需要删掉的interval让剩下的不重叠。这道题直觉上感觉可以用earliest finishing time(EFT)来做，就是尽早地释放resource给后面的interval从而找到尽可能多不重叠的interval。那么为什么EFT可以给我最优解的？贪婪最难的不是算法，大多数情况下都是证明算法的正确性，为什么它可以给出最优解。一般来讲有两个思路去证明：

1. 假设存在最优解O，这个算法的每一步都至少跟O一样或者想的更优，从而推出这个算法推出的解就是最优解
2. 假设存在某个解P，通过不断地每一步的变化可以推出最优解O的结构，而我们的算法生成的结果恰好满足这个结构

这里我们用第一种思路去证明。假设存在最优解O，最优解的第i个interval表示为O[i]。算法所推出的解为P，第i个interval表示为P[i]。那么我们一定有结论P[i].end <= O[i].end, 证明：

• 很显然对于i = 1成立
• 假设i = k成立
• 那么对于i = k + 1 的情况，由于P[k].end <= O[k].end，那么对于O[k + 1]，一定也可以放到P里，所以至少P[k + 1].end和O[k + 1].end相同，所以P[k + 1].end <= O[k + 1].end成立

根据这个结论，我们可以进一步推出P.size() >= O.size()。因为假设P包含i个intervals，O包含j个intervals(j > i)，从O[i + 1]到O[j - 1]这些intervals都可以放入集合P，因为P[i].end <= O[i].end。这和j > i矛盾。所以结论成立。P自然不可能优于最优解，所以P就是最优解。

时间复杂度O(nlogn)，代码如下：