原文链接: https://leetcode-cn.com/problems/t3fKg1

英文原文

中文题目

某实验室计算机待处理任务以 `[start,end,period]` 格式记于二维数组 `tasks`，表示完成该任务的时间范围为起始时间 `start` 至结束时间 `end` 之间，需要计算机投入 `period` 的时长，注意： 1. `period` 可为不连续时间 2. 首尾时间均包含在内

处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。

示例 1：

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]

输出：4

解释：
tasks[0] 选择时间点 2、3；
tasks[1] 选择时间点 2、3、5；
tasks[2] 选择时间点 5、6；
因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。

示例 2：

输入：tasks = [[2,3,1],[5,5,1],[5,6,2]]

输出：3

解释：
tasks[0] 选择时间点 2 或 3；
tasks[1] 选择时间点 5；
tasks[2] 选择时间点 5、6；
因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。

提示：

• 2 <= tasks.length <= 10^5
• tasks[i].length == 3
• 0 <= tasks[i][0] <= tasks[i][1] <= 10^9
• 1 <= tasks[i][2] <= tasks[i][1]-tasks[i][0] + 1

通过代码

高赞题解

做完题目后，来看了一些各位大神的题解，没发现和自己一样的做法，就和大家分享一下吧。
（解题思路本质上和@lucifer1004的题解相似）

核心分析：
1、一个任务，最晚启动时刻为：结束时刻-运行时长；
2、一堆任务里，应该最先被启动的任务，它的最晚启动时刻最小；
3、对于一堆都已经开始的任务，当系统运行a时长后，所有任务的最晚启动时刻也会集体后移a（或完成）；

算法步骤：
1、按任务的开始时间从小到大逐一加到任务池q；
2、任务池里的任务，根据它们最晚需要开始启动的时刻（结束时刻-时长-已运行时长），用最小堆维护；
3、每加入一个新任务T（ts时刻开始）前，如果任务池里的最早启动时刻qs小于ts，让系统从qs运行至ts（或到完成任务），更新系统运行总时长res；
4、为了方便T和之前任务比较谁需要更早启动，把T转化成T’（最晚启动时刻-res，时长+res），把T’加到任务池
5、当哨兵假任务添加入任务池后，所有真实任务已完成；

算法复杂度O(nlog(n))

[]
class Solution:
    def processTasks(self, tasks) -> int:
        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵
        res, q = 0, []
        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :
            while q and q[0][0]+res < s :
                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除
                else : res += min(q[0][1], s) - (q[0][0]+res)
            heapq.heappush(q, [e-p+1-res, e+1])
        return res

统计信息

通过次数	提交次数	AC比率
1115	2707	41.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言