What is the greedy approach for Set Intersection Size At Least Two?

The greedy approach involves selecting key elements from sorted intervals to ensure that at least two elements are covered for each interval, minimizing the set size.

How do I validate the set intersection for each interval?

After selecting the elements for the set, check if every interval contains at least two elements from the set. If not, adjust the set accordingly.

What is the time complexity of the Set Intersection Size At Least Two problem?

The time complexity is dominated by the sorting step, which is O(n log n), where n is the number of intervals.

Can this problem be solved without sorting the intervals?

Sorting the intervals is crucial for ensuring the greedy approach works efficiently. Without sorting, the problem would likely require more complex logic and potentially slower solutions.

What if the problem requires more than two elements in the intersection?

The solution would need to adjust the greedy strategy to select the appropriate number of elements to satisfy the new condition, but the core approach would remain similar.

#757

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

设置交集大小至少为2

给你一个二维整数数组 intervals ，其中 intervals[i] = [start i , end i ] 表示从 start i 到 end i 的所有整数，包括 start i 和 end i 。包含集合是一个名为 nums 的数组，并满足 intervals 中的每个区间都至少…

数组贪心排序

题目描述

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

包含集合 是一个名为 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 <= start_i < end_i <= 10⁸

lightbulb

解题思路

方法一：排序 + 贪心

我们希望在数轴上选出尽可能少的整数点，使得每个区间都至少包含两个点。一个经典而有效的策略是按照区间的右端点进行排序，并尽量让已选取的点位于区间的右侧，以便这些点能覆盖更多后续区间。

首先将所有区间按照如下规则排序：

按右端点从小到大；
若右端点相同，按左端点从大到小。

这样排序的原因是：右端点越小的区间“可操作空间”越少，应优先满足；当右端点相同时，左端点更大的区间更窄，更应优先被处理。

随后，我们使用两个变量 $s$ 和 $e$ 分别记录当前所有已处理区间所共同拥有的 倒数第二个点 和 最后一个点。初始时 $s = e = -1$ ，表示还没有放置任何点。

接下来依次处理排序后的区间 $[a, b]$ ，根据它与 $\{s, e\}$ 的关系分三种情况讨论：

若 $a \leq s$ ：当前区间已包含 $s$ 和 $e$ 两个点，无需额外放点。
若 $s < a \leq e$ ：当前区间只包含一个点（即 $e$ ），还需要补一个点。为了让新点对后续区间最有帮助，我们选择在区间最右侧的点 $b$ 。此时更新 $\textit{ans} = \textit{ans} + 1$ ，并将新的两点设为 $\{e, b\}$ 。
若 $a > e$ ：当前区间完全不包含已有的两个点，需要补两个点。最优选择是在区间最右侧放置 $\{b - 1, b\}$ 。此时更新 $\textit{ans} = \textit{ans} + 2$ ，并将新的两点设为 $\{b - 1, b\}$ 。

最终返回总共放置的点数 $\textit{ans}$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为区间的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0]))
        s = e = -1
        ans = 0
        for a, b in intervals:
            if a <= s:
                continue
            if a > e:
                ans += 2
                s, e = b - 1, b
            else:
                ans += 1
                s, e = e, b
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of greedy strategies and interval problems.
question_mark
The candidate considers both the sorting step and the invariant maintenance when explaining the solution.
question_mark
The candidate emphasizes validating the greedy choice and its impact on minimizing the set size.

warning

常见陷阱

外企场景

error
Choosing too few elements without validating the intersection for all intervals.
error
Failing to maintain the invariant that at least two elements must intersect each interval.
error
Not sorting the intervals properly, leading to inefficient greedy selections.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we had to make the set size exactly two for each interval?
arrow_right_alt
How would the solution change if intervals could overlap in more complex ways?
arrow_right_alt
What is the effect of a larger number of intervals on the overall set size?

help

常见问题

外企场景

继续练习

#768 最多能完成排序的块 II #769 最多能完成排序的块 #826 安排工作以达到最大收益