区间调度问题

问题概述

给定 n 个任务，每个任务有开始时间 start 和结束时间 end。两个任务不冲突当且仅当后一个任务的开始时间 >= 前一个任务的结束时间（首尾可相接）。

两种常见变体：

1. 最大任务数：每个任务权重相同，求最多能完成多少个任务 → 贪心；
2. 最大利润：每个任务有利润 profit，求最大总利润 → 动态规划 + 二分。

---

方法一：最大任务数（贪心）

思路及解法

这是经典的活动选择问题。

贪心策略：按结束时间升序排序，依次选择不冲突的任务。

为什么按结束时间排序：

• 结束得越早，留给后面任务的时间越多；
• 每次选结束最早且不冲突的任务，能为后续留下最大空间；
• 这是可以严格证明的贪心最优策略。

流程：

1. 按结束时间升序排序；
2. 维护 last_end 表示上一个被选任务的结束时间，初始为 -inf；
3. 遍历每个任务 (s, e)：
   • 若 s >= last_end，说明与已选任务不冲突，选中它，count += 1，last_end = e；
4. 返回 count。

边界说明：

• s >= last_end：允许首尾相接（闭区间不重叠）；
• 若题目要求严格不重叠（首尾不能相等），改成 s > last_end。

代码

def max_tasks(tasks: list[tuple[int, int]]) -> int:
    if not tasks:
        return 0

    # 按结束时间升序排序
    tasks.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    for s, e in tasks:
        if s >= last_end:      # 不冲突
            count += 1
            last_end = e

    return count

复杂度分析

• 时间复杂度：$O(n \log n)$，排序开销。
• 空间复杂度：$O(1)$ 或 $O(n)$（取决于排序实现）。

示例

tasks = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
# 排序后：[(1,3), (2,5), (4,7), (6,9), (8,10)]
# 选：(1,3) → (4,7) → (8,10)
# 答案：3

---

方法二：最大利润（DP + 二分）

思路及解法

每个任务有权重 profit，贪心不再成立，需要用动态规划。

状态定义：dp[i] 表示「前 i 个任务（按结束时间排序后）能获得的最大利润」。

转移方程：

对于第 i 个任务（0-indexed，对应 dp[i+1]）：

• 不选它：dp[i]；
• 选它：profit[i] + dp[k]，其中 k 是「最后一个结束时间 <= 当前任务开始时间的任务」的数量。

$$dp[i+1] = \max(dp[i],\ dp[k] + profit[i])$$

如何快速找 k：

• 把所有任务的结束时间单独拿出来，因为已按结束时间排序，所以 ends 是升序的；
• 用 bisect_right(ends, start) 找到第一个 > start 的位置 k，则 ends[0..k-1] 都 <= start，即前 k 个任务都可以作为前驱。

为什么重复的 end 不影响结果：dp[k] 表示的是「前 k 个任务」这个前缀的最优解，而不是「第 k 个任务」的解。bisect_right 按值切分，相同 end 的任务一定作为整体被划入或划出前缀，不会出现部分包含。

代码

from bisect import bisect_right

def max_profit(n: int, startTime: list[int], endTime: list[int], profit: list[int]) -> int:
    """
    n：任务数
    startTime / endTime / profit：三个等长数组
    返回最大利润
    """
    jobs = list(zip(startTime, endTime, profit))
    jobs.sort(key=lambda x: x[1])        # 按结束时间排序
    ends = [j[1] for j in jobs]          # 结束时间数组（升序）

    dp = [0] * (n + 1)                   # dp[i]：前 i 个任务的最大利润

    for i, (s, e, p) in enumerate(jobs):
        k = bisect_right(ends, s)        # ends[:k] 全部 <= s
        dp[i + 1] = max(dp[i], dp[k] + p)

    return dp[n]

复杂度分析

• 时间复杂度：$O(n \log n)$，排序 $O(n \log n)$，每次二分 $O(\log n)$，共 $n$ 次。
• 空间复杂度：$O(n)$，dp 和 ends 数组。

示例

startTime = [1, 2, 4, 6, 5]
endTime   = [3, 5, 6, 7, 8]
profit    = [50, 20, 70, 60, 30]

print(max_profit(5, startTime, endTime, profit))  # 180（选 (1,3) + (4,6) + (6,7)）

---

带路径还原（打印选了哪些任务）

思路及解法

dp 数组本身就完整记录了「选没选」的信息，无需额外的 pre 数组：

• 若 dp[i] == dp[i-1]：说明「不选任务 i-1」也能达到最优利润，跳过它，i -= 1；
• 若 dp[i] > dp[i-1]：说明最优解一定选了任务 i-1，把它加入结果，然后跳到它的前驱范围。

为什么「选了」时要跳 k 步：

k = bisect_right(ends, start)，start 是任务 i-1 的开始时间：

• ends[0..k-1] <= start：前 k 个任务都不与任务 i-1 冲突，可以作为前驱；
• ends[k..i-2] > start：从第 k 个到第 i-2 个任务都与任务 i-1 冲突，不能同时选。

因此选了任务 i-1 后，接下来能选的只能是前 k 个任务，i = k 正好跳到这个范围。

注意：由于 dp[i] > dp[i-1] 说明 dp[i] = dp[k] + p，所以是直接从 dp[k] 这个前缀最优解继续，无需关心 k 到 i-2 之间的任务。

终止性：k <= i-1 < i，每次 i 严格减小，回溯一定终止。

代码

from bisect import bisect_right

def max_profit_with_tasks(jobs: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
    if not jobs:
        return 0, []

    jobs.sort(key=lambda x: x[1])
    n = len(jobs)
    ends = [j[1] for j in jobs]

    dp = [0] * (n + 1)

    for i, (s, e, p) in enumerate(jobs):
        k = bisect_right(ends, s)
        dp[i + 1] = max(dp[i], dp[k] + p)

    # 回溯
    i = n
    chosen = []
    while i > 0:
        if dp[i] == dp[i - 1]:
            i -= 1                          # 没选任务 i-1
        else:
            chosen.append(jobs[i - 1])
            k = bisect_right(ends, jobs[i - 1][0])
            i = min(k, i - 1)               # 保证 i 严格递减
    chosen.reverse()

    return dp[n], chosen

示例

jobs = [(1, 3, 50), (2, 4, 70), (5, 6, 60)]
best, chosen = max_profit_with_tasks(jobs)
print(best)     # 130
print(chosen)   # [(2, 4, 70), (5, 6, 60)]

复杂度分析

• 时间复杂度：$O(n \log n)$。
• 空间复杂度：$O(n)$，dp 和 ends 两个数组。

---

两种问题对比

	最大任务数	最大利润
权重	每个任务权重为 1	每个任务有独立利润
方法	贪心（按结束时间排序）	DP + 二分
时间	$O(n \log n)$	$O(n \log n)$
空间	$O(1)$	$O(n)$
核心	早结束优先	选或不选取最大

关键区别：当所有任务价值相同时，贪心最优；一旦引入不同利润，贪心不再成立，必须用 DP。

---

边界条件说明

1. 首尾能否相接

• 代码中统一用 s >= last_end（或 bisect_right），表示首尾可以相接；
• 若题目要求「严格不重叠」（即前一个任务结束时间必须 < 后一个开始时间），把 >= 改为 >，bisect_right 改为 bisect_left。

2. 利润可能为负

• dp[0] = 0 表示「一个任务都不选」，利润为 0；
• 若某些任务利润为负，DP 会自动选择不选它们，无需特殊处理。

3. end == start 的退化任务

若任务长度为 0（end == start），回溯时 bisect_right(ends, start) 可能返回 k >= i，导致 i = k 不严格递减，死循环。

防御写法：

i = min(k, i - 1)

或者提前过滤掉 end <= start 的任务（视题目是否允许）。

4. 任务允许并行

• 上述两种方法都假设同一时间只能执行一个任务；
• 若允许多台机器并行，问题变成「会议室 II」类型，需要求最大重叠数（扫描线 / 最小堆），与本文不同。

---

总结

• 最大任务数：贪心，按结束时间排序，依次选不冲突的，$O(n \log n)$；
• 最大利润：DP + 二分，dp[i+1] = max(dp[i], dp[k] + profit[i])，$O(n \log n)$；
• 路径还原：无需额外数组，直接用 dp[i] 与 dp[i-1] 比较判断是否选中；选中后跳到 k；
• 重复 end 不影响正确性：dp[k] 是前缀最优解，bisect_right 按值切分，相同值作为整体划分；
• 边界：首尾是否可相接决定用 >= / >，以及 bisect_right / bisect_left；注意 end == start 的死循环风险；
• 通用套路：区间调度 → 按结束时间排序，无权贪心，有权 DP。

相关题目

• LC 435. 无重叠区间（贪心，求最少删除数）
• LC 452. 用最少数量的箭引爆气球（贪心）
• LC 253. 会议室 II（扫描线 / 最小堆，允许并行）
• LC 1235. 规划兼职工作（加权区间调度，本题原型）
• LC 646. 最长数对链（贪心 / DP）