T2589.完成所有任务的最少时间

greedy, https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/

你有一台电脑，它可以同时运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。

当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。

请你返回完成所有任务的情况下，电脑最少需要运行多少秒。

示例 1：

输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
输出：2
解释：
- 第一个任务在闭区间 [2, 2] 运行。
- 第二个任务在闭区间 [5, 5] 运行。
- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
电脑总共运行 2 个整数时间点。

示例 2：

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
输出：4
解释：
- 第一个任务在闭区间 [2, 3] 运行
- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
- 第三个任务在闭区间 [5, 6] 运行。
电脑总共运行 4 个整数时间点。

提示：

1 <= tasks.length <= 2000
tasks[i].length == 3
1 <= starti, endi <= 2000
1 <= durationi <= endi - starti + 1

这道题的核心思想是贪心算法。

解题思路

贪心策略：为了让电脑运行的总时间最少，我们应该尽可能让多个任务在同一个时间点运行。
排序：我们将所有任务按照结束时间 endi 从小到大进行排序。
- 原因：当我们处理一个任务时，为了让它的运行时间点能尽量被后面的任务复用，我们应该优先选择该任务区间内靠后的时间点。因为后面的任务结束时间更晚，靠后的时间点更有可能落在后面任务的区间内。
具体步骤：
- 创建一个布尔数组 run（长度为 2001），记录每个时间点电脑是否开机。
- 遍历排序后的任务：
  1. 统计当前任务区间 [starti, endi] 内已经有多少个时间点已经开机了（这些点可以被当前任务复用）。
  2. 如果已开机的时间点不足 durationi，则从区间从后往前遍历，找到未开机的时间点进行开机，直到满足 durationi。
结果：统计 run 数组中 True 的个数。

代码实现

python

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        # 1. 按照结束时间从小到大排序
        tasks.sort(key=lambda x: x[1])
        
        # 2. 记录每个时间点是否开机，范围是 1 到 2000
        # 题目提示 start, end <= 2000
        run = [False] * 2001
        
        for start, end, duration in tasks:
            # 3. 统计当前区间 [start, end] 内已经运行了多少秒
            count = 0
            for i in range(start, end + 1):
                if run[i]:
                    count += 1
            
            # 4. 如果运行时间不够，需要补充
            if count < duration:
                needed = duration - count
                # 5. 贪心策略：从后往前找空闲时间点补齐
                # 这样做是为了让这些时间点尽量落在后续任务的区间内
                for i in range(end, start - 1, -1):
                    if not run[i]:
                        run[i] = True
                        needed -= 1
                        if needed == 0:
                            break
                            
        # 6. 返回总的运行时间点数量
        return sum(run)

复杂度分析

时间复杂度： $O (N \log N + N \times M)$ 。其中 $N$ 是任务数量（最大 2000）， $M$ 是时间范围（最大 2000）。
- 排序消耗 $O (N \log N)$ 。
- 遍历任务并扫描区间消耗 $O (N \times M)$ 。
- 在 $N, M \leq 2000$ 的情况下，计算量级约在 $4 \times 10^{6}$ ，在 Python 的执行时限内。
空间复杂度： $O (M)$ 。需要一个长度为 2001 的数组来记录状态。

进阶（如果数据范围更大）

如果 $N$ 和 $M$ 的范围达到 $10^{5}$ ，上述 $O (N M)$ 的方法会超时。那时我们需要使用树状数组 (Fenwick Tree) 或 线段树 (Segment Tree) 来优化区间统计和区间更新的操作，将复杂度降低到 $O (N \log M)$ 。但对于本题的约束，贪心+暴力模拟是最简洁的解法。

T2589.完成所有任务的最少时间 ​

T2589.完成所有任务的最少时间