这道题我们可以观察出如下几点，对于两个区间i1和i2：
- 如果区间i1包含区间i2，那么我们可以直接将remove i1而不需要考虑它，因为最终结果i2肯定至少也有两个元素被选，那么i1肯定也满足条件
- 如果i1和i2没有交集，那么两个区间各自取两个数
- 如果i1和i2正好头尾相交，比如i1 = [1,3], i2 = [3,6]，那么我们只需要在交点处取一个，之后在i1和i2中各取一个
- 如果i2和i2相交并且相交的区间大于等于2，我们只需要在相交的部分取两个即可
对于情况1，我们只需要做一个preprocess，用stack来帮我们remove包含的情况。具体做法是，我们按照start排序interval，如果当前栈顶元素i1.end 大于等于当前元素i2.end，我们pop出i1即可。这样可以保证我们不会出现1中情况。那么现在的问题是，对于2、3、4的情况，我们应该如何在区间中取数呢？
经过preprocess之后，现在已经不存在1的情况，我们按照start排序，然后依次取出interval。如果我们发现需要在当前区间取数，那么我们取尽量靠右边的数，这样的话，对于下一个区间，其能够重复利用的可能性是最大的。也就说，假设已经在i1中取了数并且满足题目要求，对于i2来说：
- 如果是情况2，我们在i2的最右端取两个数
- 如果是情况2和3：
- 假设区间覆盖的部分没有包含i1取的数，同情况2
- 假设区间覆盖的部分包含i1取的数：
- 如果包含了1个，在i2最右端取一个
- 如果包含了2个，i2就不要取了
也就是说，我们每次要记录并更新上一次取的两个数的位置。假设有n个区间，算法时间复杂度O(n * log n)，空间复杂度O(n)，代码如下：
No comments:
Post a Comment