2589. Minimum Time to Complete All Tasks
Description
There is a computer that can run an unlimited number of tasks at the same time. You are given a 2D integer array tasks
where tasks[i] = [starti, endi, durationi]
indicates that the ith
task should run for a total of durationi
seconds (not necessarily continuous) within the inclusive time range [starti, endi]
.
You may turn on the computer only when it needs to run a task. You can also turn it off if it is idle.
Return the minimum time during which the computer should be turned on to complete all tasks.
Example 1:
Input: tasks = [[2,3,1],[4,5,1],[1,5,2]] Output: 2 Explanation: - The first task can be run in the inclusive time range [2, 2]. - The second task can be run in the inclusive time range [5, 5]. - The third task can be run in the two inclusive time ranges [2, 2] and [5, 5]. The computer will be on for a total of 2 seconds.
Example 2:
Input: tasks = [[1,3,2],[2,5,3],[5,6,2]] Output: 4 Explanation: - The first task can be run in the inclusive time range [2, 3]. - The second task can be run in the inclusive time ranges [2, 3] and [5, 5]. - The third task can be run in the two inclusive time range [5, 6]. The computer will be on for a total of 4 seconds.
Constraints:
1 <= tasks.length <= 2000
tasks[i].length == 3
1 <= starti, endi <= 2000
1 <= durationi <= endi - starti + 1
Solutions
Solution 1: Greedy + Sorting
We observe that the problem is equivalent to selecting $duration$ integer time points in each interval $[start,..,end]$, so that the total number of selected integer time points is minimized.
Therefore, we can first sort $tasks$ in ascending order of end time $end$. Then we greedily make selections. For each task, we start from the end time $end$ and choose the points as late as possible from back to front. This way, these points are more likely to be reused by later tasks.
In our implementation, we can use an array $vis$ of length $2010$ to record whether each time point has been selected. Then for each task, we first count the number of points $cnt$ that have been selected in the interval $[start,..,end]$, and then select $duration - cnt$ points from back to front, while recording the number of selected points $ans$ and updating the $vis$ array.
Finally, we return $ans$.
The time complexity is $O(n \times \log n + n \times m)$, and the space complexity is $O(m)$. Here, $n$ and $m$ are the lengths of $tasks$ and $vis$ array, respectively. In this problem, $m = 2010$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|