[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)，代码如下：

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	int eraseOverlapIntervals(vector<Interval>& intervals) {
	if(intervals.empty())return 0;
	int n = intervals.size();
	sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2) { return i1.end < i2.end;});
	int count = 1, end = intervals[0].end;
	for(int i = 1; i < n; ++i)
	{
	if(intervals[i].start < end)
	continue;
	else
	{
	++count;
	end = intervals[i].end;
	}
	}
	return n - count;
	}
	};

view raw Non-overlapping Intervals.cpp hosted with ❤ by GitHub