Drawbridge OA

Leetcode 757 Set Intersection Size At Least Two

https://leetcode.com/articles/set-intersection-size-at-least-two/

解法：greedy解法
网上solution很多，但是大多数都写得不好。贪心算法这种东西不证明正确性（每一步取最优导致全局最优）是不能随便瞎用的。
唯一写的好的帖子是https://discuss.leetcode.com/topic/115912/ever-wonder-why-the-greedy-algorithm-works-here-is-the-explanation 解释了为什么这个贪心算法reasonable.

重要的观察点。

1. intervals[0，i]的minimal intersection set S_i 与intervals里面的各个subarray的顺序没有关系。e.g. [[1,2],[3,4],[5,6]] 和 [[3,4],[1,2],[5,6]]的minimal intersection set没有区别。这就意味着我们可以改变intervals中各个interval的顺序
2. S_(i-1) <= S_{i}.这个表达式导致了每一步如何求解最优解：S_{i}>=S_(i-1)很重要 (如果等号能够取到那最好S_{i}=S_(i-1)， 否则就分情况S_{i}=S_(i-1)/+1/+2，之后变成最优解)。（是不是想到了djikstra里面dist[u] + w(u,v) <= dist[v]，如果满足的话，dist[v]已经是最优解，否则用dist[u] + w(u,v)代替做最优 ） 。
   • 这个不等式的证明很简单，如果S_i < S_(i-1)的话，那么显然S_i应该也跟intervals[0,i-1]的所有interval全部至少有两个intersection，而S_i居然size比S_(i-1)小，这显然与S_(I-1)的定义矛盾。所以不等式得证。

greedy algorithms的实现：

1. 排序，2.从
   • interval的后端点升序，后端点等同的情况下前段点降序（总是先处理更短的那个interval，所以之前选的S_i-1点也被后面的所包含。）。这样子已知intervals[0,i-1]的S_i，interval[I]的后端点必然大于等于S_i中的最大值，从而得到取等号的条件是S_i最大的两个值比跟interval[i]相交。
   • 如果S_i-1最大值两个值中只有1个与interval[i]相交则 S_i >=1+S_(I-1)。 （S_i-1中其余元素必然不与interval[i]相交，毕竟它们连S_i-1次大的元素都不如）。而且等号一定可以取到，就是从interval[i]中取一个加入S_(i-1) => S_(i),.---这里我们取interval[i]中最大的元素加进去。尽量促进S[i]和S[i+1] 能够取等号。
   • 同理，S_i-1最大值中没有与interval[i]相交则S_i >=2+S_i-1 .取interval[I]最大的两个元素加进去就好。