2589. Minimum Time to Complete All Tasks
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.
What are the most two important steps in writing a depth first search function? (Select 2)
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
tasksby their end times, which is done using Python'ssortmethod with a lambda function defining the sorting key asx[1], wherexis each task andx[1]represents the end time of each task.1tasks.sort(key=lambda x: x[1]) -
Initializing the timeline: An array
visis 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.1vis = [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 thedurationof the task accordingly.1duration -= sum(vis[start : end + 1]) -
Filling in the remaining duration: We iterate from the task's
endtime down to itsstarttime, and for each unit of time, if it has not been used (if not vis[i]), we decrease the remainingduration, mark the time point as used (vis[i] = 1), and increment theanscount indicating the computer was turned on for another time unit.1i = end 2while i >= start and duration > 0: 3 if not vis[i]: 4 duration -= 1 5 vis[i] = 1 6 ans += 1 7 i -= 1 -
Returning the result: After processing all tasks,
ansholds 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.
Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
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:
1Task 1: [1, 4, 3] 2Task 2: [2, 6, 2] 3Task 3: [5, 8, 1]
Step 1: Sort the tasks by their end times. After sorting:
1Task 1: [1, 4, 3] 2Task 2: [2, 6, 2] 3Task 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.
1vis = [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 invisand reducedurationto 0. Theanscount is now 3.
1vis = [..., 0, 1, 1, 1, 0, 0, ...] # '...' represents unchanged values; index 2 to 4 are marked as 1. 2ans = 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 incrementansto 4.
1vis = [..., 0, 1, 1, 1, 0, 1, 0, ...] # Now index 6 is also marked as 1. 2ans = 4
- For Task 3
[5, 8, 1], we start from time 8. It's free, so we mark it as used, andansincrements to 5.
1vis = [..., 0, 1, 1, 1, 0, 1, 0, 1, ...] # Index 8 is marked as 1. 2ans = 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
401import 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}
421#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};
461function 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}
34What's the relationship between a tree and a graph?
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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.