What is the main approach for Minimum Time to Complete All Tasks?

The primary strategy is binary search over possible active durations combined with sorting tasks by end time and greedy allocation.

Can tasks be split across non-continuous seconds?

Yes, each task can be executed in multiple segments within its allowed time window, which is essential for minimizing active time.

Why sort tasks by end time?

Sorting by end time ensures that greedy allocation can fill later slots first, reducing conflicts and helping binary search find feasible schedules efficiently.

How does binary search over valid answers work here?

Binary search tests candidate total active times; for each, a scheduling simulation checks whether all tasks can be completed within the candidate duration.

What are common mistakes in this problem?

Typical errors include double-counting active seconds, ignoring non-continuous execution, and failing to properly track allocated slots during feasibility checks.

#2589

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

完成所有任务的最少时间

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

数组二分查找栈贪心排序

题目描述

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

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

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

示例 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 <= start_i, end_i <= 2000
1 <= duration_i <= end_i - start_i + 1

lightbulb

解题思路

方法一：贪心 + 排序

我们观察发现，题目相当于在每一个区间 $[start,..,end]$ 中，选择 $duration$ 个整数时间点，使得总共选择的整数时间点最少。

因此，我们可以先对 $tasks$ 按照结束时间 $end$ 从小到大排序。然后贪心地进行选择，对于每一个任务，我们从结束时间 $end$ 开始，从后往前选择尽可能靠后的点，这样这些点更有可能被后面的任务重复利用。

我们在实现上，可以用一个长度为 $2010$ 的数组 $vis$ 记录每个时间点是否被选择过。然后对于每一个任务，我们先统计 $[start,..,end]$ 区间内已经被选择过的点的个数 $cnt$ ，然后从后往前选择 $duration - cnt$ 个点，同时记录选择的点的个数 $ans$ 以及更新 $vis$ 数组。

最后，我们返回 $ans$ 即可。

时间复杂度 $O(n \times \log n + n \times m)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别为 $tasks$ 的长度和 $vis$ 数组的长度。本题中 $m = 2010$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1])
        vis = [0] * 2010
        ans = 0
        for start, end, duration in tasks:
            duration -= sum(vis[start : end + 1])
            i = end
            while i >= start and duration > 0:
                if not vis[i]:
                    duration -= 1
                    vis[i] = 1
                    ans += 1
                i -= 1
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the number of tasks and the range of possible active durations; sorting adds O(n log n), binary search adds O(log(maxTime)), and scheduling feasibility checks add O(n*maxDuration). Space complexity depends on tracking scheduled seconds, which may require O(maxEnd) arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting by end time hints at a greedy or scheduling approach.
question_mark
Binary search over the answer space signals optimization beyond naive simulation.
question_mark
Attention to non-continuous task allocation is critical for passing edge cases.

warning

常见陷阱

外企场景

error
Failing to account for tasks split across non-continuous time windows can underestimate required active time.
error
Using naive simulation without sorting can lead to incorrect schedules and timeouts.
error
Not updating or tracking already allocated seconds properly can result in double-counting active time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Tasks have fixed durations but allow preemption in arbitrary time slices within the window.
arrow_right_alt
Compute minimum active time with additional constraints like maximum simultaneous tasks.
arrow_right_alt
Change the problem to maximize tasks completed within a fixed total active time.

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2616 最小化数对的最大差值 #2554 从一个范围内选择最多整数 I