1834. Single-Threaded CPU
Problem Description
In this problem, we are given a number n
representing the number of tasks and a 2D integer array called tasks
, where each subarray tasks[i]
contains two elements [enqueueTimei, processingTimei]
. The first element, enqueueTimei
, indicates the time at which the i
-th task becomes available to the CPU for processing. The second element, processingTimei
, represents the time required to complete this task.
The CPU is single-threaded, meaning it can only process one task at a time. In deciding which task to process, the CPU follows these rules:
- If the CPU is idle and no tasks are available, it remains idle.
- If the CPU is idle and there are available tasks, it chooses the task with the shortest
processingTime
. If there is a tie inprocessingTime
, it selects the task with the smaller index. - The CPU will process the entire task without interruption once it begins.
- The CPU can start a new task instantly after finishing one.
The objective is to return the order in which the CPU will process the tasks.
Intuition
To arrive at the solution for this problem, we need to simulate the CPU task processing in the order defined by its operation rules. We need to tackle a few key aspects:
-
Task Sorting: Since we are interested in the order in which tasks become available (
enqueueTime
), we first sort all tasks based on this value. However, since we also need to track the original index of each task, we append this index to each task before sorting. -
Priority Queue: To efficiently select the next task to process according to processing time (and index in case of ties), we use a priority queue or a min-heap. This data structure allows us to have the desired task at the top and can be retrieved in constant time.
-
Task Management: We iterate through the tasks, and if a task is available (
enqueueTime
<= current time), we add it to the priority queue. If no tasks are available or being processed, we fast forward the current time to the nextenqueueTime
. -
Processing Tasks: When the CPU is ready to process a new task (either because it is idle or has finished the last task), we pop the top task from the priority queue (which has the shortest
processingTime
and smallest index in case of a tie), process it, and add its original index to the answer list. -
Time Advancement: As we process each task, we advance the current time by the
processingTime
of the task we just processed.
The loop continues until all tasks have been processed and the priority queue is empty. The output is the ans
list that keeps track of the tasks' original indexes in the order they were processed, which is our final solution.
Learn more about Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution to this task scheduling problem involves implementing a simulation based on CPU scheduling rules. Here's a walk-through of the implementation:
-
Appending Task Indexes: The initial step involves appending an index to each task array to keep track of the original order of the tasks. This is achieved with a simple
enumerate
loop:for i, task in enumerate(tasks): task.append(i)
After this step, each
task
intasks
has the format[enqueueTime, processingTime, index]
. -
Sorting Tasks: Prior to processing, tasks are sorted based on their
enqueueTime
because that determines when a task becomes available:tasks.sort()
This initial sort ensures that we consider tasks in the order they become available for processing.
-
Priority Queue via Min-Heap: To pick the next task to be processed efficiently, the code uses a priority queue (implemented with a
heapq
in Python). This queue orders tasks byprocessingTime
andindex
when there is a tie. -
Processing Loop: The processing loop functions as the main control flow of the algorithm, determining when to add tasks to the queue, process tasks or advance time:
while q or i < n: if not q: t = max(t, tasks[i][0]) while i < n and tasks[i][0] <= t: heappush(q, (tasks[i][1], tasks[i][2])) i += 1 pt, j = heappop(q) ans.append(j) t += pt
This loop continues until all tasks have been processed.
-
Time Management and Task Selection:
- If the queue is empty (
not q
), the current timet
is set to the next task'senqueueTime
if the current time is earlier than that. - Tasks are added to the priority queue if their
enqueueTime
is less than or equal to the current timet
. Since the priority queue is a min-heap, tasks are ordered, taking into account both theirprocessingTime
andindex
in case of ties. - The next task (
pt
,j
) is popped off from the priority queue, andj
, which represents the original index of the task, is appended to the answer listans
. - The current time
t
is incremented by theprocessingTime
of the task that just finished processing (pt
).
- If the queue is empty (
-
Answer List: The result of the algorithm is contained in the
ans
list. This list tracks the original indexes of the tasks in the order they were processed by the CPU based on the described scheduling rules.
After the loop finishes executing, the ans
list is returned, providing the order in which the CPU will process the tasks.
To sum up, we make use of a combination of sorting, a heap-based priority queue, and careful management of the tasks as per CPU scheduling rules to arrive at the desired output.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach. Suppose the number n
is 3
, representing that there are three tasks, and the tasks
array is given as [[0, 3], [1, 9], [2, 6]]
.
Here, each subarray represents a task where the first element is the enqueueTime
and the second element is the processingTime
.
-
Appending Task Indexes: We append the index to each task. Now the
tasks
array becomes:[[0, 3, 0], [1, 9, 1], [2, 6, 2]]
-
Sorting Tasks: After sorting the tasks based on
enqueueTime
, our array remains the same:[[0, 3, 0], [1, 9, 1], [2, 6, 2]]
-
Priority Queue Initialization: We initialize an empty priority queue (min-heap) for selecting tasks by shortest
processingTime
. -
Processing Loop: Now, we simulate the CPU processing with a loop:
- The current time
t
is initially0
. - We start with the first task
tasks[0]
which hasenqueueTime
of0
andprocessingTime
of3
. - Since the CPU is idle at
t=0
, it immediately picks up the first task.
- The current time
-
Time Management and Task Selection: While the CPU processes the first task:
- The first task
tasks[0]
is processed from timet=0
tot=3
. - The second task
tasks[1]
is now available (sincet
is now3
), and it's enqueued in the priority queue. - The third task
tasks[2]
is also now available and enqueued in the priority queue.
- The first task
-
Priority Queue Selection: The CPU is ready for the next task at
t=3
:- The priority queue now contains
[tasks[1], tasks[2]]
or[[9, 1], [6, 2]]
. - The task with the shortest
processingTime
is selected, which istasks[2]
(processingTime=6
).
- The priority queue now contains
-
Processing the Next Task:
- Task
tasks[2]
is processed from timet=3
tot=9
. - Now, the next task in the priority queue is
tasks[1]
which is the only one left.
- Task
-
Task Completion: Process the last task:
- Task
tasks[1]
withprocessingTime
of9
is processed fromt=9
tot=18
.
- Task
The CPU has now finished processing all the tasks. The order in which tasks were processed and their indexes are recorded as [0, 2, 1]
.
To sum up, the CPU processed the tasks as per their enqueueTime
and processingTime
, using a priority queue to manage the processing order. The original order of task processing based on CPU rules is [0, 2, 1]
for this example.
Solution Implementation
1from typing import List
2import heapq
3
4class Solution:
5 def getOrder(self, tasks: List[List[int]]) -> List[int]:
6 # Add task index to each task for later reference
7 for index, task in enumerate(tasks):
8 task.append(index)
9
10 # Sort tasks based on their enqueue time
11 tasks.sort()
12
13 # Initialize the answer list and a priority queue
14 answer = []
15 priority_queue = []
16
17 # Initialize pointers and variables for task processing and time tracking
18 num_tasks = len(tasks)
19 task_index = 0
20 current_time = 0
21
22 # Process all tasks
23 while priority_queue or task_index < num_tasks:
24 # If the priority queue is empty, jump to the next task's enqueue time
25 if not priority_queue:
26 current_time = max(current_time, tasks[task_index][0])
27
28 # Add all tasks that can be processed at the current time to the priority queue
29 while task_index < num_tasks and tasks[task_index][0] <= current_time:
30 heapq.heappush(priority_queue, (tasks[task_index][1], tasks[task_index][2]))
31 task_index += 1
32
33 # Pop the task with the lowest processing time from the priority queue
34 processing_time, task_order_index = heapq.heappop(priority_queue)
35
36 # Append the task index to the answer list
37 answer.append(task_order_index)
38
39 # Increment the current time by the task's processing time
40 current_time += processing_time
41
42 # Return the processed order of task indices
43 return answer
44
1import java.util.PriorityQueue;
2import java.util.Arrays;
3
4class Solution {
5 public int[] getOrder(int[][] tasks) {
6 int numberOfTasks = tasks.length;
7 int[][] enrichedTasks = new int[numberOfTasks][3];
8
9 // Enrich the tasks with their original index
10 for (int i = 0; i < numberOfTasks; ++i) {
11 enrichedTasks[i] = new int[] {tasks[i][0], tasks[i][1], i};
12 }
13
14 // Sort tasks by their enqueue time
15 Arrays.sort(enrichedTasks, (task1, task2) -> task1[0] - task2[0]);
16
17 // Prepare the answer array
18 int[] taskOrder = new int[numberOfTasks];
19
20 // Initialize a priority queue to determine the order of execution
21 // Sort by processing time, if equal, sort by index
22 PriorityQueue<int[]> taskQueue
23 = new PriorityQueue<>((task1, task2) -> task1[0] == task2[0] ? task1[1] - task2[1] : task1[0] - task2[0]);
24
25 // Initialize pointers
26 int taskIndex = 0;
27 int currentTime = 0;
28 int orderIndex = 0;
29
30 // Process the tasks
31 while (!taskQueue.isEmpty() || taskIndex < numberOfTasks) {
32 if (taskQueue.isEmpty()) {
33 // Update current time to the next task's enqueue time if the queue is empty
34 currentTime = Math.max(currentTime, enrichedTasks[taskIndex][0]);
35 }
36 // Enqueue the tasks that have become available by current time
37 while (taskIndex < numberOfTasks && enrichedTasks[taskIndex][0] <= currentTime) {
38 taskQueue.offer(new int[] {enrichedTasks[taskIndex][1], enrichedTasks[taskIndex][2]});
39 ++taskIndex;
40 }
41
42 // Poll the task with smallest processing time; if equal, with smaller index
43 int[] nextTask = taskQueue.poll();
44 // Set the task index in completion order
45 taskOrder[orderIndex++] = nextTask[1];
46 // Increase the current time by the task's processing time
47 currentTime += nextTask[0];
48 }
49
50 return taskOrder;
51 }
52}
53
1#include <vector>
2#include <queue>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 // Function to simulate the task scheduling process
9 vector<int> getOrder(vector<vector<int>>& tasks) {
10 int numTasks = tasks.size(); // Number of tasks
11
12 // Add an index to each task for tracking
13 for (int i = 0; i < numTasks; ++i) {
14 tasks[i].push_back(i);
15 }
16
17 // Sort the tasks by their enqueue time
18 sort(tasks.begin(), tasks.end());
19
20 // Define a min-heap to keep the tasks by their processing time and index
21 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> taskQueue;
22
23 vector<int> order; // This will store the final order of completed tasks
24 long long currentTime = 0; // Current time in the simulation
25 int taskIndex = 0; // Index to track up to which task has been added to the heap
26
27 // Repeat until all tasks are processed
28 while (!taskQueue.empty() || taskIndex < numTasks) {
29 // If the queue is empty, jump to the next task's start time
30 if (taskQueue.empty()) {
31 currentTime = max(currentTime, static_cast<long long>(tasks[taskIndex][0]));
32 }
33
34 // Add all tasks that can be started at or before the current time to the heap
35 while (taskIndex < numTasks && tasks[taskIndex][0] <= currentTime) {
36 int processTime = tasks[taskIndex][1];
37 int originalIndex = tasks[taskIndex][2];
38
39 // Add to the min-heap with processing time and original index
40 taskQueue.push({processTime, originalIndex});
41 ++taskIndex; // Move to the next task in the list
42 }
43
44 // Pop the task with the smallest processing time (and smallest index in case of ties)
45 auto [processingTime, index] = taskQueue.top();
46 taskQueue.pop();
47
48 // Add the index of the task to the order of completion
49 order.push_back(index);
50
51 // Advance the current time by the task's processing time
52 currentTime += processingTime;
53 }
54 return order; // Return the order in which the tasks get processed
55 }
56};
57
1// Importing necessary utilities from 'typescript-collections'
2import { PriorityQueue } from 'typescript-collections';
3
4// Represents a single task with its start time, processing time, and original index
5type Task = [number, number, number];
6
7// Function to compare two tasks based on their processing time and indexes
8function compareTasks(a: Task, b: Task): number {
9 if (a[1] !== b[1]) return a[1] - b[1]; // Compare by processing time
10 return a[2] - b[2]; // Compare by original index
11}
12
13// Function to simulate the task scheduling process
14function getOrder(tasks: Task[]): number[] {
15 const numTasks: number = tasks.length; // Number of tasks
16
17 // Add an index to each task for tracking
18 tasks.forEach((task, index) => {
19 task.push(index);
20 });
21
22 // Sort the tasks by their enqueue time
23 tasks.sort((a, b) => a[0] - b[0]);
24
25 // Define a min-heap to keep the tasks by their processing time and index
26 const taskQueue = new PriorityQueue<Task>(compareTasks);
27
28 const order: number[] = []; // This will store the final order of completed tasks
29 let currentTime: number = 0; // Current time in the simulation
30 let taskIndex: number = 0; // Index to track up to which task has been added to the heap
31
32 // Repeat until all tasks are processed
33 while (!taskQueue.isEmpty() || taskIndex < numTasks) {
34 // If the queue is empty, jump to the next task's start time
35 if (taskQueue.isEmpty()) {
36 currentTime = Math.max(currentTime, tasks[taskIndex][0]);
37 }
38
39 // Add all tasks that can be started at or before the current time to the heap
40 while (taskIndex < numTasks && tasks[taskIndex][0] <= currentTime) {
41 const task = tasks[taskIndex];
42 // Add to the min-heap with processing time and original index
43 taskQueue.enqueue(task);
44 taskIndex++; // Move to the next task in the list
45 }
46
47 // Pop the task with the smallest processing time (and smallest index in case of ties)
48 const task = taskQueue.dequeue();
49 if (task) {
50 const [processingTime, , originalIndex] = task;
51
52 // Add the index of the task to the order of completion
53 order.push(originalIndex);
54
55 // Advance the current time by the task's processing time
56 currentTime += processingTime;
57 }
58 }
59 return order; // Return the order in which the tasks get processed
60}
61
Time and Space Complexity
Time Complexity
The given code snippet sorts the tasks based on their enqueue time and then uses a min-heap to manage the processing order based on their processing time and index. The time complexity can be broken down as follows:
- Sorting the
tasks
list takesO(n log n)
time, wheren
is the number of tasks. - The while loop runs for at most
2n
iterations (each task is pushed and popped exactly once), and the two nested while loops each run forn
iterations in total over the course of the algorithm, notn
per outer iteration. The resulting amortized cost per task for the operations within these loops isO(log n)
for each heap push and pop operation.
Combining these parts, the overall time complexity of the code is O(n log n)
due to the sort operation and the heap operations.
Space Complexity
The space complexity is determined by the space required to store the tasks
list with extra index information and the heap:
- The
tasks
list, with an appended index for each task, takesO(n)
space. - The heap,
q
, which in the worst case can store all tasks at once if their enqueue times are identical, also takesO(n)
space.
Therefore, the total space complexity is O(n)
, as both the modified task list and the heap scale linearly with the number of tasks.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!