LeetCode 2589. Minimum Time to Complete All Tasks Solution in Java, C++, Python & More | Explanation + Code

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 × log n + n × 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.

PythonJavaC++GoTypeScriptRust

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(code-box)

class Solution { public int findMinimumTime(int[][] tasks) { Arrays.sort(tasks, (a, b) -> a[1] - b[1]); int[] vis = new int[2010]; int ans = 0; for (var task : tasks) { int start = task[0], end = task[1], duration = task[2]; for (int i = start; i <= end; ++i) { duration -= vis[i]; } for (int i = end; i >= start && duration > 0; --i) { if (vis[i] == 0) { --duration; ans += vis[i] = 1; } } } return ans; } }(code-box)

class Solution { public: int findMinimumTime(vector<vector<int>>& tasks) { sort(tasks.begin(), tasks.end(), [&](auto& a, auto& b) { return a[1] < b[1]; }); bitset<2010> vis; int ans = 0; for (auto& task : tasks) { int start = task[0], end = task[1], duration = task[2]; for (int i = start; i <= end; ++i) { duration -= vis[i]; } for (int i = end; i >= start && duration > 0; --i) { if (!vis[i]) { --duration; ans += vis[i] = 1; } } } return ans; } };(code-box)

func findMinimumTime(tasks [][]int) (ans int) { sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] }) vis := [2010]int{} for _, task := range tasks { start, end, duration := task[0], task[1], task[2] for _, x := range vis[start : end+1] { duration -= x } for i := end; i >= start && duration > 0; i-- { if vis[i] == 0 { vis[i] = 1 duration-- ans++ } } } return }(code-box)

function findMinimumTime(tasks: number[][]): number { tasks.sort((a, b) => a[1] - b[1]); const vis: number[] = Array(2010).fill(0); let ans = 0; for (let [start, end, duration] of tasks) { for (let i = start; i <= end; ++i) { duration -= vis[i]; } for (let i = end; i >= start && duration > 0; --i) { if (vis[i] === 0) { --duration; ans += vis[i] = 1; } } } return ans; }(code-box)

impl Solution { pub fn find_minimum_time(tasks: Vec<Vec<i32>>) -> i32 { let mut tasks = tasks; tasks.sort_by(|a, b| a[1].cmp(&b[1])); let mut vis = vec![0; 2010]; let mut ans = 0; for task in tasks { let start = task[0] as usize; let end = task[1] as usize; let mut duration = task[2] - vis[start..=end].iter().sum::<i32>(); let mut i = end; while i >= start && duration > 0 { if vis[i] == 0 { duration -= 1; vis[i] = 1; ans += 1; } i -= 1; } } ans } }(code-box)