Readme

757.Set-Intersection-Size-At-Least-Two

我们想象如果我们能找出一系列non-overlapping的区间，那么我们的答案必然需要在每个区间内至少采集两点。所以本题的答案至少是maximum number of non-overlapping intervals的两倍。所以借鉴435的思路，我们采用sort by ending points的方法去下手。这个突破口的想法和452.Minimum-Number-of-Arrows-to-Burst-Balloons很相似。

如果我们将这些区间按照后边界从小到大排序后（相同后边界的情况下，显然只考虑区间跨度最短的，因为短区间能被S覆盖的话，那么相同右端点的长区间必然也能被覆盖），先考虑第一个区间。对于这个区间，我们肯定会选该区间的最后两点加入S，因为这两点是最有可能与后面的区间重合的，效率最高。

然后我们再考虑下一个区间[x,y]，此时S应该如何更新呢？一个最明显的特点是，y一定大于等于S里的最大点。于是此时最有影响的其实就只是区间的前边界a。我们分类讨论x的位置查看对S的影响：

1. 如果[x,y]覆盖了S最后两个点，那么S就不用更新；
2. 如果[x,y]只覆盖了S最后一个点，那么这个点其实就一定是S的后边界，那么S需要再补一个点。这个点是什么呢?最好的选择就是[x,y]的最后一个点，即y。这种做法是最“贪心”的，因为它最可能会与[x,y]之后的区间重合。
3. 如果[x,y]没有覆盖S，那么S就要加上什么呢，是[x,y]的最后两个点即可，同理也是用贪心的策略。

综上，我们其实只要每次关注集合S里的最大两个点a，b即可，不断与下一个区间[x,y]考察相对关系，更新S。

Leetcode Link