AJohn Blog

外观

10.2 区间贪心

约 1957 字大约 7 分钟

2025-05-23

区间贪心有如下经典问题：

  • 不相交区间（单机器调度/活动安排）：给定一些区间，从中选出尽量多的两两互不相交的区间。
  • 区间分组（任务调度/会议室）：给定一些区间，把这些区间分成最少的组，使得每组内的区间互不相交。
  • 区间选点（射气球，Interval Stabbing）：给定一些区间，在数轴上放置最少的点，使得每个区间都包含至少一个点。最少要放置多少个点？
  • 区间覆盖（灌溉花园）：给定一些区间，从中选出尽量少的区间，覆盖一条指定线段 [s,t]。

任务：总结上述四种区间贪心问题的解法，尤其是排序的规则和理由，什么时候要按照左端点排序？什么时候要按照右端点排序？排序的目的是什么？

10.2.1 不相交区间

  1. 435. 无重叠区间

    给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
    示例 1：

    输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
    输出: 1
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

    提示

    思路：按照右端点的大小排序，第一个一定是要的，后面的区间如果左端点大于等于上一个区间的右端点也满足，同时更新右端点。

    class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1]) # O(nlogn)
    res = 0
    pre_right = float('-inf')
    for i, j in intervals: # O(n)
        if i >= pre_right:
            res += 1
            pre_right = j
    return len(intervals) - res

    时间复杂度：O(nlogn)O(nlogn)，其中 n 为 intervals 的长度。

    空间复杂度：O(1)O(1)，忽略排序的栈开销。

  2. 646. 最长数对链

    给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。找出并返回能够形成的 最长数对链的长度 。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
    示例 1：

    输入：pairs = [[1,2], [2,3], [3,4]]
    输出：2
    解释：最长的数对链是 [1,2] -> [3,4] 。

    提示

    思路：和上一题一样，只不过大于等于换成了大于。

    class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
    pairs.sort(key=lambda x: x[1]) # O(nlogn)
    res = 0
    pre_right = -inf
    for i, j in pairs: # O(n)
        if i > pre_right:
            res += 1
            pre_right = j
    return res

    时间复杂度：O(nlogn)O(nlogn)，其中 n 为 pairs 的长度。

    空间复杂度：O(1)O(1)，忽略排序的栈开销。

10.2.2 区间分组

  1. 2406. 将区间分为最少组数

    给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。请你返回 最少 需要划分成多少个组。如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
    示例 1：

    输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
    输出：3
    解释：我们可以将区间划分为如下的区间组：

    • 第 1 组：[1, 5] ，[6, 8] 。
    • 第 2 组：[2, 3] ，[5, 10] 。
    • 第 3 组：[1, 10] 。
      可以证明无法将区间划分为少于 3 个组。

    提示

    思路：

    时间复杂度：

    空间复杂度：

10.2.3 区间选点

本质上和不相交区间是一样的。

  1. 452. 用最少数量的箭引爆气球

    有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
    示例 1：

    输入：points = [[10,16],[2,8],[1,6],[7,12]]
    输出：2
    解释：气球可以用2支箭来爆破:
    -在x = 6处射出箭，击破气球[2,8]和[1,6]。
    -在x = 11处发射箭，击破气球[10,16]和[7,12]。

    提示

    思路：排序右端点，我们在右端点射箭，如果下一个区间的左端点在右端点左边，则可以节省一只箭，否则在下一个区间的右端点新建一只箭。

    class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
    points.sort(key=lambda x: x[1]) # O(nlogn)
    res = 0
    pre_right = -inf
    for i, j in points: # O(n)
        if i > pre_right:
            res += 1
            pre_right = j
    return res

    时间复杂度：O(nlogn)O(nlogn)，其中 n 为 points 的长度。

    空间复杂度：O(1)O(1)，忽略排序的栈开销。

10.2.4 区间覆盖

  1. 45. 跳跃游戏 II

    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 0 <= j <= nums[i]， i + j < n；返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
    示例 1：

    输入: nums = [2,3,1,1,4]
    输出: 2
    解释: 跳到最后一个位置的最小跳跃数是 2。
    从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

    提示

    思路：见灵神题解。

    class Solution:
def jump(self, nums: List[int]) -> int:
    cur_right = 0
    next_right = 0
    res = 0
    for i in range(len(nums) - 1): # O(n)
        next_right = max(nums[i] + i, next_right)
        if cur_right == i:
            res += 1
            cur_right = next_right
    return res

    时间复杂度：O(n)O(n)，其中 n 为 nums 的长度。

    空间复杂度：O(1)O(1)。