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:

  1. If the CPU is idle and no tasks are available, it remains idle.
  2. If the CPU is idle and there are available tasks, it chooses the task with the shortest processingTime. If there is a tie in processingTime, it selects the task with the smaller index.
  3. The CPU will process the entire task without interruption once it begins.
  4. 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:

  1. 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.

  2. 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.

  3. 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 next enqueueTime.

  4. 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.

  5. 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:

  1. 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:

    1for i, task in enumerate(tasks):
    2    task.append(i)

    After this step, each task in tasks has the format [enqueueTime, processingTime, index].

  2. Sorting Tasks: Prior to processing, tasks are sorted based on their enqueueTime because that determines when a task becomes available:

    1tasks.sort()

    This initial sort ensures that we consider tasks in the order they become available for processing.

  3. 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 by processingTime and index when there is a tie.

  4. 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:

    1while q or i < n:
    2    if not q:
    3        t = max(t, tasks[i][0])
    4    while i < n and tasks[i][0] <= t:
    5        heappush(q, (tasks[i][1], tasks[i][2]))
    6        i += 1
    7    pt, j = heappop(q)
    8    ans.append(j)
    9    t += pt

    This loop continues until all tasks have been processed.

  5. Time Management and Task Selection:

    • If the queue is empty (not q), the current time t is set to the next task's enqueueTime 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 time t. Since the priority queue is a min-heap, tasks are ordered, taking into account both their processingTime and index in case of ties.
    • The next task (pt, j) is popped off from the priority queue, and j, which represents the original index of the task, is appended to the answer list ans.
    • The current time t is incremented by the processingTime of the task that just finished processing (pt).
  6. 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.

Example 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.

  1. Appending Task Indexes: We append the index to each task. Now the tasks array becomes:

    1[[0, 3, 0], [1, 9, 1], [2, 6, 2]]
  2. Sorting Tasks: After sorting the tasks based on enqueueTime, our array remains the same:

    1[[0, 3, 0], [1, 9, 1], [2, 6, 2]]
  3. Priority Queue Initialization: We initialize an empty priority queue (min-heap) for selecting tasks by shortest processingTime.

  4. Processing Loop: Now, we simulate the CPU processing with a loop:

    • The current time t is initially 0.
    • We start with the first task tasks[0] which has enqueueTime of 0 and processingTime of 3.
    • Since the CPU is idle at t=0, it immediately picks up the first task.
  5. Time Management and Task Selection: While the CPU processes the first task:

    • The first task tasks[0] is processed from time t=0 to t=3.
    • The second task tasks[1] is now available (since t is now 3), and it's enqueued in the priority queue.
    • The third task tasks[2] is also now available and enqueued in the priority queue.
  6. 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 is tasks[2] (processingTime=6).
  7. Processing the Next Task:

    • Task tasks[2] is processed from time t=3 to t=9.
    • Now, the next task in the priority queue is tasks[1] which is the only one left.
  8. Task Completion: Process the last task:

    • Task tasks[1] with processingTime of 9 is processed from t=9 to t=18.

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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:

  1. Sorting the tasks list takes O(n log n) time, where n is the number of tasks.
  2. 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 for n iterations in total over the course of the algorithm, not n per outer iteration. The resulting amortized cost per task for the operations within these loops is O(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:

  1. The tasks list, with an appended index for each task, takes O(n) space.
  2. The heap, q, which in the worst case can store all tasks at once if their enqueue times are identical, also takes O(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.


Recommended Readings


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.


TA 👨‍🏫