2589. Minimum Time to Complete All Tasks

HardStackGreedyArrayBinary SearchSorting

Problem Description

In this task scheduling problem, we are given a list of tasks, each with a start time, end time, and a duration indicating how long the task needs to run. The computer can run these tasks simultaneously, and we have the flexibility to turn the computer on and off as needed. Our goal is to figure out the minimum amount of time the computer needs to be active (turned on) to accomplish all the tasks within their respective time ranges.

To visualize this problem, think of each task as a window of time during which it can be performed. The computer must be turned on long enough to "cover" these windows cumulatively. Since tasks can overlap in time, we want to make sure we are efficient about when we are running the computer to minimize the total on time.

Intuition

The intuition behind the solution approach is to manage the scheduling of tasks in a way that maximizes the overlap of their execution windows, hence reducing the total time the computer is on. To achieve this, we sort the tasks based on their end time. This allows us to prioritize the completion of tasks that need to be finished sooner.

Next, we try to select time points for each task starting from the task's end time and moving backwards to fill in its required duration. This increases the likelihood that the computer's operating time for one task will also count towards the operating times of subsequent tasks, essentially reusing time points. This greedy approach ensures that we do not unnecessarily turn on the computer earlier than needed for any given task.

To keep track of which time points have already been scheduled, we use an array vis as a timeline, marking off time points that have been allocated. For each task, we first determine how many of its required time points are already covered by other tasks (scheduled previously), and then we fill in the remaining duration as needed. The total number of "turned on" time points, ans, gives us the minimum time the computer needs to be active. After iterating through all tasks in this manner and updating the timeline (vis array), the final value of ans will be our desired minimum on time.

By being strategic about the order in which we choose time points for tasks and by optimizing for overlap, we arrive at a solution that minimizes the computer's active time while ensuring all tasks are completed within their respective time windows.

Learn more about Stack, Greedy, Binary Search and Sorting patterns.

Solution Approach

The solution uses a greedy algorithm, a common pattern for optimization problems where we build up a solution piece by piece, selecting the most optimal choice at each step. In this case, sorting tasks by their end times and selecting time points for each task from end to start qualifies as such a choice. The underlying data structures used are a simple list for tracking tasks and an array (list) for recording which time points have already been selected.

Here's a step-by-step breakdown of the implementation:

Sorting tasks: We sort the tasks by their end times, which is done using Python's sort method with a lambda function defining the sorting key as x[1], where x is each task and x[1] represents the end time of each task.
```
tasks.sort(key=lambda x: x[1])
```
Initializing the timeline: An array vis is created with a sufficient size (2010 is chosen to cover the range of possible timestamps), initialized to 0s, indicating that no time points have been used yet.
```
vis = [0] * 2010
```
Greedy time point selection: For each task, we determine how many time points are already covered (sum(vis[start:end + 1])) and reduce the duration of the task accordingly.
```
duration -= sum(vis[start : end + 1])
```

Filling in the remaining duration: We iterate from the task's end time down to its start time, and for each unit of time, if it has not been used (if not vis[i]), we decrease the remaining duration, mark the time point as used (vis[i] = 1), and increment the ans count indicating the computer was turned on for another time unit.

i = end
while i >= start and duration > 0:
    if not vis[i]:
        duration -= 1
        vis[i] = 1
        ans += 1
    i -= 1

Returning the result: After processing all tasks, ans holds the total number of time points selected, which is the minimum time the computer needs to be on.

The strategy ensures that if a time point can serve multiple tasks, it will be used for all of them, reducing the total number of distinct time points, and thus, the total time the computer needs to be on. By iterating from the end of the task's window towards the start, we prioritize later usage over earlier, which aligns with our sorted task list and makes it more likely to reuse time points for subsequent tasks.

The overall time complexity of the algorithm is O(n * k), where n is the number of tasks, and k is the average range of the tasks (end - start). It is dominated by the time taken to find the sum of visited time points for each task and attempting to fill its remaining duration which might involve iterating over the range of the task.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simplified example to illustrate the solution approach. Assume we have 3 tasks that need to be scheduled, with each task represented as [start time, end time, duration].

Task List:

Task 1: [1, 4, 3]
Task 2: [2, 6, 2]
Task 3: [5, 8, 1]

Step 1: Sort the tasks by their end times. After sorting:

Task 1: [1, 4, 3]
Task 2: [2, 6, 2]
Task 3: [5, 8, 1]

The tasks are already sorted by their end times.

Step 2: Initialize the timeline (vis) as an array with sufficient size.

vis = [0] * 2010  # 2010 is just for example purposes and assumes no times will exceed this value.

Step 3: Move through the tasks one by one and try to cover each task's duration, starting from its end time.

For Task 1 [1, 4, 3], we start from time 4. Since no other task is scheduled yet, we mark times 4, 3, and 2 as used in vis and reduce duration to 0. The ans count is now 3.

vis = [..., 0, 1, 1, 1, 0, 0, ...]  # '...' represents unchanged values; index 2 to 4 are marked as 1.
ans = 3

For Task 2 [2, 6, 2], we see that time 2 is already used by Task 1. We only need to schedule Task 2 for one more unit of time. We use time 6, mark it as used, and increment ans to 4.

vis = [..., 0, 1, 1, 1, 0, 1, 0, ...]  # Now index 6 is also marked as 1.
ans = 4

For Task 3 [5, 8, 1], we start from time 8. It's free, so we mark it as used, and ans increments to 5.

vis = [..., 0, 1, 1, 1, 0, 1, 0, 1, ...]  # Index 8 is marked as 1.
ans = 5

Step 4: After all tasks have been scheduled, ans is 5, which means the minimum time the computer needs to be active is 5 units.

Summary: The tasks overlap between time 2 and 4, so the computer only needs to be active for a total of 5 time units to cover all tasks, even though the sum of individual task durations is 6. The greedy approach successfully minimized the computer's on time by scheduling overlapping tasks simultaneously.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMinimumTime(self, tasks: List[List[int]]) -> int:
5        # Sort tasks by the end time
6        tasks.sort(key=lambda x: x[1])
7
8        # Initialize a list to keep track of visited time slots, assuming the maximum end time is less than 2010
9        visited = [0] * 2010
10
11        # Initialize answer to count the minimum time required to finish all tasks
12        minimum_time_required = 0
13
14        # Iterate over each task
15        for start_time, end_time, duration in tasks:
16            # Decrease duration by the number of already visited time slots within the task's window
17            duration -= sum(visited[start_time:end_time + 1])
18
19            # Initialize a pointer at the end time of the current task
20            i = end_time
21
22            # Check if we can place the task in the current window and still need more duration
23            while i >= start_time and duration > 0:
24                # If the time slot is not yet visited
25                if not visited[i]:
26                    # Decrease the remaining duration since we are using this time slot
27                    duration -= 1
28
29                    # Mark this time slot as visited
30                    visited[i] = 1
31
32                    # Increment the minimum time required since we've occupied another time slot
33                    minimum_time_required += 1
34
35                # Move to the previous time slot and repeat till the start time or the task duration is met
36                i -= 1
37
38        # Return the computed minimum time required to finish all tasks
39        return minimum_time_required
40

1import java.util.Arrays;
2
3class Solution {
4  
5    public int findMinimumTime(int[][] tasks) {
6        // Sort the tasks based on their end times
7        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
8      
9        // Initialize an array to track the usage of each time slot
10        int[] visits = new int[2010];
11      
12        // Initialize an answer variable to keep the count of visited time slots
13        int ans = 0;
14      
15        // Iterate through each task
16        for (int[] task : tasks) {
17            int startTime = task[0]; // Start time of the current task
18            int endTime = task[1]; // End time of the current task
19            int duration = task[2]; // Duration of the current task needs in terms of unvisited time slots
20          
21            // Decrease duration for each visited time slot within the task's time range
22            for (int i = startTime; i <= endTime; i++) {
23                duration -= visits[i];
24                if (duration < 0) {
25                    duration = 0; // Duration shouldn't be less than 0
26                }
27            }
28          
29            // Allocate unvisited time slots starting from the end time of the task
30            for (int i = endTime; i >= startTime && duration > 0; i--) {
31                if (visits[i] == 0) { // If time slot is unvisited
32                    --duration; // Decrement the remaining duration
33                    ans += visits[i] = 1; // Visit this time slot and increment the answer
34                }
35            }
36        }
37      
38        // Return the total number of visited time slots used to execute all tasks
39        return ans;
40    }
41}
42

1#include <vector>
2#include <algorithm> // For sort
3#include <bitset>
4
5class Solution {
6public:
7    // Function to find the minimum time to complete all tasks
8    int findMinimumTime(vector<vector<int>>& tasks) {
9        // Sort the tasks by their end time in ascending order
10        sort(tasks.begin(), tasks.end(), [&](const auto& a, const auto& b) { return a[1] < b[1]; });
11
12        // Initialize a bitset to keep track of visited time slots, assuming maximum 2010 slots
13        bitset<2010> visited;
14
15        // Initialize the answer to store the minimum number of time slots required
16        int minimumTimeRequired = 0;
17
18        // Iterate over each task to schedule them
19        for (const auto& task : tasks) {
20            // Extracting the start time, end time and duration for each task
21            int startTime = task[0];
22            int endTime = task[1];
23            int duration = task[2];
24
25            // Calculate the amount of duration that can be allocated within the time window
26            for (int i = startTime; i <= endTime; ++i) {
27                // Reduce duration for already visited time slots within the window
28                duration -= visited[i];
29            }
30
31            // Assign time slots for remaining duration in reverse order to meet end time
32            for (int i = endTime; i >= startTime && duration > 0; --i) {
33                // If the time slot is not yet visited
34                if (!visited[i]) {
35                    // Decrease remaining duration and mark this time slot as visited
36                    --duration;
37                    minimumTimeRequired += visited[i] = 1;
38                }
39            }
40        }
41
42        // Return the computed minimum time required to complete all tasks
43        return minimumTimeRequired;
44    }
45};
46

1function findMinimumTime(tasks: number[][]): number {
2  // Sort the tasks array by end time in ascending order
3  tasks.sort((taskA, taskB) => taskA[1] - taskB[1]);
4
5  // Create an array to keep track of visited times, initialized with zeros
6  const visited = new Array(2010).fill(0);
7
8  // Initialize the answer variable to count the minimum time needed to complete tasks
9  let minimumTime = 0;
10
11  // Iterate through each task to find the minimum time necessary
12  for (let task of tasks) {
13    const [startTime, endTime, taskDuration] = task; // Destructure task details
14
15    let remainingDuration = taskDuration; // Initialize remaining task duration
16
17    // Calculate the remaining duration after considering previously visited time slots
18    for (let time = startTime; time <= endTime; ++time) {
19      remainingDuration -= visited[time];
20    }
21
22    // Fill the time slots from end to start respecting the task duration
23    for (let time = endTime; time >= startTime && remainingDuration > 0; --time) {
24      if (visited[time] === 0) {
25        --remainingDuration; // Decrease remaining duration as we fill the time slot
26        minimumTime += visited[time] = 1; // Mark the time slot as visited and increment minimum time
27      }
28    }
29  }
30
31  // Return the computed minimum time necessary to complete the tasks
32  return minimumTime;
33}
34

Time and Space Complexity

Time Complexity

The given code sorts the tasks list, which takes O(NlogN) time, where N is the number of tasks.

After sorting, the code iterates through each task with a nested while loop. In the worst case, for each task, the while loop could iterate from end to start, which could be O(M), where M is the range of possible start and end times.

As a rough upper bound, this nested iteration could result in the inner operation being executed N * M times, since for each of 'N' tasks, the while loop could potentially iterate 'M' times (where 'M' is the largest possible end time — in this case, 2010). However, because each time unit can only be visited once due to the vis condition, the total number of operations of the inner loop is bounded by 'M' across all tasks. This makes the nested while loop take O(M) in total.

Summing these two parts, the overall time complexity is O(NlogN + M). Note that in practice, M is bounded by a constant (2010), so if we consider M to be a constant, then the time complexity simplifies to O(NlogN).

Space Complexity

The space consumed by the solution includes the storage for the visited time units vis, which has a fixed size based on the problem constraints (2010), and the internal space used for the sorted array of tasks. Therefore, the space complexity is O(M + N). If M is considered to be a constant due to its fixed upper bound, then the space complexity simplifies to O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know