日期: 2025 年 11 月 20 日

目标

给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。

• 例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。

返回包含集合可能的最小大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。

示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。 

示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。 

说明：

• 1 <= intervals.length <= 3000
• intervals[i].length == 2
• 0 <= starti < endi <= 10^8

思路

定义包含集合是 与 intervals 中每个区间的交集大小至少为 2 的集合，求包含集合的最小 size。

根据 intervals 中每个区间的起点排序，倒序遍历区间，对于最后一个区间，显然优先选最左边的 2 个元素最优，将其按照从大到小顺序加入包含列表，接着访问下一个区间，判断包含集合的最小的两个元素是否在当前区间内：

• 如果都在，直接跳过
• 如果都不在，将当前区间左侧前两个元素按从大到小顺序加入包含列表
• 如果只有一个在，需要比较当前区间左端点 l 与包含集合最小元素 min 的关系，如果 min > l 将 l 加入列表，否则（即 min == l，由于是按起点排序的，所以 min 不会小于 l），用 l + 1 替换原来的列表最后一个元素，然后将 l 加入列表

代码

/**
 * @date 2025-11-20 8:46
 */
public class IntersectionSizeTwo757 {

    public int intersectionSizeTwo(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<Integer> res = new ArrayList<>();
        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            if (p == 0 || res.get(p - 1) > r) {
                res.add(l + 1);
                res.add(l);
                p += 2;
            } else if (p > 1 && res.get(p - 2) > r) {
                if (res.get(p - 1) == l) {
                    res.set(p - 1, l + 1);
                }
                res.add(l);
                p++;
            }
        }
        return res.size();
    }

}

性能