原文链接: https://leetcode-cn.com/problems/set-intersection-size-at-least-two

英文原文

An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b.

Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has a size of at least two.

 

Example 1:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.

Example 2:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: An example of a minimum sized set is {1, 2, 3, 4, 5}.

 

Constraints:

• 1 <= intervals.length <= 3000
• intervals[i].length == 2
• 0 <= ai < bi <= 108

中文题目

一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.

注意:

1. intervals 的长度范围为[1, 3000]。
2. intervals[i] 长度为 2，分别代表左、右边界。
3. intervals[i][j] 的值是 [0, 10^8]范围内的整数。

通过代码

官方题解

方法一：贪心算法

让我们先尝试解决一个更简单的问题：当设置的交集大小至少为 1 时，我们该怎么做。

将区间排序，取最后一个区间 [s，e]，在该区间上的哪个点会在 S？由于每个区间都有起点 <=s，所以我们先取 s 作为 S 的元素。然后去掉所有包含 s 的区间。

当设置的交集大小至少为 2 时，我们尝试将该方案扩展。

算法：

对于每个间隔，我们将执行上述算法，todo 存储的是还需的交集元素个数，当我们确定一个点在 S 时，我们将根据情况更新 todo。

一个重要的例子：[[1, 2], [2, 3], [2, 4], [4, 5]]。在处理 [4，5] 时，将 4，5 放到 S 中；在处理 [2，4] 时，将 2 放到 S 中；在处理 [2，3] 时，我们需要将 3 放到 S 中，而不是放 2，因为 2 已经放进去过了。

我们可以将区间 [s，e] 按 s 升序，当 s 相同时，按 e 降序来解决上述情况。这样可以在遇到相同 s 的区间，都包含最小的 e。因此这样有最高的多重性。在处理的 [s，e] 时（s 与之前不同），可以保证区间的开始（s 或 s，s+1）将始终是未使用的。

[solution1-Python]
class Solution(object):
    def intersectionSizeTwo(self, intervals):
        intervals.sort(key = lambda (s, e): (s, -e))
        todo = [2] * len(intervals)
        ans = 0
        while intervals:
            (s, e), t = intervals.pop(), todo.pop()
            for p in xrange(s, s+t):
                for i, (s0, e0) in enumerate(intervals):
                    if todo[i] and p <= e0:
                        todo[i] -= 1
                ans += 1
        return ans

[solution1-Java]
class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (a, b) ->
                    a[0] != b[0] ? a[0]-b[0] : b[1]-a[1]);
        int[] todo = new int[intervals.length];
        Arrays.fill(todo, 2);
        int ans = 0, t = intervals.length;
        while (--t >= 0) {
            int s = intervals[t][0];
            int e = intervals[t][1];
            int m = todo[t];
            for (int p = s; p < s+m; ++p) {
                for (int i = 0; i <= t; ++i)
                    if (todo[i] > 0 && p <= intervals[i][1])
                        todo[i]--;
                ans++;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(N^2)$。其中 $N$ 为 intervals 的长度。
• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
2576	6082	42.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言