LeetCode 2589 - Minimum Time to Complete All Tasks

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Stack, Greedy, Sorting

Solution

Problem Understanding

This problem is asking us to determine the minimum amount of time that a computer must be turned on to execute a set of tasks, given that each task has a specified time window [starti, endi] and requires a total duration durationi that does not need to be continuous. In other words, the computer can run multiple tasks simultaneously, and we can selectively choose when to turn it on within each task's allowed time window to minimize total runtime.

The input tasks is a 2D array where each subarray [starti, endi, durationi] represents a task. The expected output is a single integer, which represents the total number of seconds the computer must be on to satisfy all tasks.

The constraints indicate that there can be up to 2000 tasks, and each task's time range can go up to 2000. This rules out naive approaches that try to simulate each second for every task individually, since that could be too slow.

Important edge cases include:

Tasks that overlap entirely or partially, requiring careful scheduling to avoid turning on the computer unnecessarily.
Tasks whose duration equals their total range, meaning the computer must be on for every second in that range.
Tasks with very small or very large ranges relative to their duration.

Approaches

Brute Force

A brute-force approach would attempt to simulate every second within the maximum possible time window (from the smallest starti to the largest endi) and track which tasks are still incomplete at each second. For every second, we could decide whether turning on the computer helps complete any remaining tasks and update their remaining durations. While this approach would produce the correct answer, it would be extremely slow because the time window can be as large as 2000, and iterating over 2000 tasks for each second could lead to an O(N * maxTime) solution, which is impractical for the constraints.

Optimal Approach

The key insight is that tasks can be scheduled greedily from the latest possible time backwards. By sorting tasks by their end time, we ensure that we fill the latest available slots first, which avoids unnecessary early activation. We maintain a boolean array to track which seconds the computer is already on. For each task, we calculate how many seconds are already covered, and if the task still requires more time, we greedily turn on the computer at the latest possible available times within its range until its duration requirement is satisfied. This ensures we always minimize the number of seconds the computer is on while satisfying all tasks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N * maxTime)	O(maxTime)	Simulates every second in the time range and checks all tasks
Optimal	O(N * maxDuration)	O(maxTime)	Sort by end time and greedily fill from the latest available times

Algorithm Walkthrough

Initialize a boolean array used of size slightly larger than the maximum end time, representing whether the computer is turned on at each second.
Sort the tasks by their endi in ascending order.
Iterate through each task [starti, endi, durationi].
Count how many seconds in the task's range are already marked as used. This gives the number of seconds already covered for this task.
If the task still needs additional time to reach its duration, greedily turn on the computer starting from endi backward, marking unused seconds as used, until the required duration is satisfied.
Continue to the next task.
After processing all tasks, sum the total number of seconds marked as used and return this value.

Why it works: Sorting tasks by end time guarantees that when we schedule additional seconds, we do not conflict with tasks that end later. Filling from the latest available time ensures we minimize overlaps and avoid turning on the computer unnecessarily early. This greedy strategy guarantees a minimal total on-time.

Python Solution

from typing import List

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        max_time = max(task[1] for task in tasks)
        used = [False] * (max_time + 2)
        
        # Sort tasks by end time
        tasks.sort(key=lambda x: x[1])
        
        for start, end, duration in tasks:
            covered = sum(used[start:end+1])
            need = duration - covered
            # Greedily fill from end backwards
            t = end
            while need > 0:
                if not used[t]:
                    used[t] = True
                    need -= 1
                t -= 1
        
        return sum(used)

Explanation: We first find the maximum endi to size our used array. After sorting tasks by end time, we iterate through each task and count already covered seconds. For any remaining duration, we mark seconds as used starting from the latest available time backward. Finally, summing used gives the minimum on-time.

Go Solution

func findMinimumTime(tasks [][]int) int {
    maxTime := 0
    for _, task := range tasks {
        if task[1] > maxTime {
            maxTime = task[1]
        }
    }

    used := make([]bool, maxTime+2)

    // Sort tasks by end time
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i][1] < tasks[j][1]
    })

    for _, task := range tasks {
        start, end, duration := task[0], task[1], task[2]
        covered := 0
        for t := start; t <= end; t++ {
            if used[t] {
                covered++
            }
        }
        need := duration - covered
        t := end
        for need > 0 {
            if !used[t] {
                used[t] = true
                need--
            }
            t--
        }
    }

    total := 0
    for _, u := range used {
        if u {
            total++
        }
    }
    return total
}

Explanation: The Go version mirrors the Python implementation. The main differences are slice initialization, loop syntax, and explicit sort.Slice for sorting. The algorithm logic remains identical.

Worked Examples

Example 1

Tasks: [[2,3,1],[4,5,1],[1,5,2]]

Sort by end: [[2,3,1],[4,5,1],[1,5,2]]
Task [2,3,1]: no seconds used in [2,3], mark 3 → used = {3}
Task [4,5,1]: no seconds used in [4,5], mark 5 → used = {3,5}
Task [1,5,2]: already covered seconds = 2 (3,5), need 0 more → done
Total used seconds = 2

Example 2

Tasks: [[1,3,2],[2,5,3],[5,6,2]]

Sort by end: [[1,3,2],[2,5,3],[5,6,2]]
Task [1,3,2]: no seconds used in [1,3], mark 3 and 2 → used = {2,3}
Task [2,5,3]: covered seconds = 2 (2,3), need 1 more → mark 5 → used = {2,3,5}
Task [5,6,2]: covered seconds = 1 (5), need 1 more → mark 6 → used = {2,3,5,6}
Total used seconds = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N * D)	Sorting takes O(N log N), iterating over tasks and potentially checking up to D = duration per task for marking used times
Space	O(T)	`used` array of size equal to the maximum end time T

The time complexity is reasonable because N and T are at most 2000. Space is also linear in the maximum time.

Test Cases

# Provided examples
assert Solution().findMinimumTime([[2,3,1],[4,5,1],[1,5,2]]) == 2  # Example 1
assert Solution().findMinimumTime([[1,3,2],[2,5,3],[5,6,2]]) == 4  # Example 2

# Edge cases
assert Solution().findMinimumTime([[1,1,1]]) == 1  # single second task
assert Solution().findMinimumTime([[1,2,2]]) == 2  # duration equals range
assert Solution().findMinimumTime([[1,2,1],[2,3,1],[3,4,1]]) == 3  # consecutive overlapping tasks
assert Solution().findMinimumTime([[1,5,3],[2,4,2]]) == 3  # overlapping tasks, greedy picks latest
assert Solution().findMinimumTime([[1,2000,1],[2,2000,1]]) == 2  # sparse tasks over large range

Test	Why
[[2,3,1],[4,5,1],[1,5,2]]	Basic example with multiple tasks and overlapping options
[[1,3,2],[2,5,3],[5,6,2]]