Single-Threaded CPU

Med

#1676Time: O(n^2), where n is the number of tasks. The main loop runs `n` times. Inside, finding available tasks and then the best task among them can take up to O(n) time in each iteration, leading to a quadratic time complexity.Space: O(n) to store the `processed` status of each task and the `result` array.2 companies

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

DoorDash IBM

Prompt

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem statement without using any advanced data structures for optimization. It iterates through time, and at each step where the CPU is free, it scans all tasks to determine which ones are available and then scans the available tasks again to find the one with the shortest processing time.

Algorithm

Initialize currentTime = 0, a boolean array processed of size n to track completed tasks, and an integer array result to store the output.
Loop n times, as we need to select n tasks in total.
In each iteration, find the set of tasks that are available to be processed. A task i is available if it's not yet processed (processed[i] is false) and its enqueueTime is less than or equal to currentTime.
Case 1: No tasks are available. If the set of available tasks is empty, the CPU is idle. We must advance time. Find the minimum enqueueTime among all unprocessed tasks and set currentTime to this value. Then, repeat step 3 to find available tasks at this new time.
Case 2: Tasks are available. From the set of available tasks, iterate through them to find the best one to execute. The best task is the one with the minimum processingTime. If there's a tie in processingTime, choose the one with the smaller original index.
Once the best task (say, index j) is identified, add j to the result array.
Mark task j as processed by setting processed[j] = true.
Update currentTime by adding the processingTime of task j to it.
Repeat the loop until n tasks have been added to the result array.

Walkthrough

The brute-force method involves a main loop that runs n times, once for each task to be scheduled. Inside this loop, we perform a linear scan over the entire tasks array to find all tasks that are currently available (i.e., their enqueue time is not later than the current time). If no tasks are available, we advance the current time to the earliest arrival time of any remaining task. From the pool of available tasks, we perform another linear scan to select the one with the minimum processing time, breaking ties with the task's original index. This selected task is added to our result, and the current time is updated. This process repeats until all tasks are scheduled.

1class Solution {2    public int[] getOrder(int[][] tasks) {3        int n = tasks.length;4        int[] result = new int[n];5        boolean[] processed = new boolean[n];6        long currentTime = 1;7        int resultIndex = 0;8 9        while (resultIndex < n) {10            int bestTaskIndex = -1;11            long minProcessingTime = Long.MAX_VALUE;12            13            // Find the best available task at the current time14            for (int i = 0; i < n; i++) {15                if (!processed[i] && tasks[i][0] <= currentTime) {16                    if (tasks[i][1] < minProcessingTime) {17                        minProcessingTime = tasks[i][1];18                        bestTaskIndex = i;19                    } else if (tasks[i][1] == minProcessingTime) {20                        if (i < bestTaskIndex) {21                            bestTaskIndex = i;22                        }23                    }24                }25            }26 27            // If no task is available, CPU is idle. Fast-forward time.28            if (bestTaskIndex == -1) {29                long nextEnqueueTime = Long.MAX_VALUE;30                for (int i = 0; i < n; i++) {31                    if (!processed[i]) {32                        nextEnqueueTime = Math.min(nextEnqueueTime, tasks[i][0]);33                    }34                }35                currentTime = nextEnqueueTime;36            } else { // Process the best task found37                result[resultIndex++] = bestTaskIndex;38                processed[bestTaskIndex] = true;39                currentTime += tasks[bestTaskIndex][1];40            }41        }42        return result;43    }44}

Complexity

Time

O(n^2), where n is the number of tasks. The main loop runs `n` times. Inside, finding available tasks and then the best task among them can take up to O(n) time in each iteration, leading to a quadratic time complexity.

Space

O(n) to store the `processed` status of each task and the `result` array.

Trade-offs

Pros

Simple to understand as it directly models the problem's rules.
Requires minimal complex data structures.

Cons

Highly inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.

This optimal approach improves efficiency by avoiding repeated scans of the task list. We first sort the tasks by their enqueueTime. Then, we simulate the process using a Min-Heap (Priority Queue) to maintain the pool of available tasks. The heap allows us to efficiently retrieve the task with the shortest processing time in O(log n) time, which is a significant improvement over the O(n) scan in the brute-force method.

Algorithm

Augment and Sort: Since the original index is needed for tie-breaking and the final output, we first transform the input tasks array. Create a new array of objects or arrays, where each element stores [enqueueTime, processingTime, originalIndex]. Sort this new array based on enqueueTime in ascending order.
Initialize Data Structures:
- A Min-Heap (Priority Queue) to store available tasks. The heap will order tasks first by processingTime (ascending) and then by originalIndex (ascending) for tie-breaking.
- A result array to store the final order of task indices.
- A variable currentTime (as a long to prevent overflow), initialized to 0.
- A pointer taskIndex to traverse the sorted tasks array, initialized to 0.
Processing Loop: Loop until the result array is full (i.e., all n tasks have been scheduled).
- Add Available Tasks: Add all tasks from the sorted array whose enqueueTime is less than or equal to currentTime into the min-heap. Increment taskIndex as you add them.
- Check CPU State:
  - If the min-heap is empty, it means the CPU is idle. Fast-forward currentTime to the enqueueTime of the next task in the sorted list (sortedTasks[taskIndex][0]).
  - If the min-heap is not empty, the CPU is busy. Poll the task with the highest priority (shortest processingTime/smallest index) from the heap.
- Update State: Add the polled task's originalIndex to the result array. Advance currentTime by the task's processingTime.
Return Result: Once the loop completes, the result array contains the correct processing order.

Walkthrough

The key idea is to process events in chronological order. Sorting tasks by enqueueTime ensures we consider tasks as they become available. A min-heap is the perfect data structure for managing the set of available tasks, as it always provides the next task to be processed (shortest processingTime, then smallest index) in logarithmic time.

We maintain a currentTime variable. The main loop continues until all tasks are scheduled. In each phase, we first add all tasks that have become available (enqueueTime <= currentTime) from our sorted list into the min-heap. If the heap is empty, the CPU is idle, so we jump currentTime to the arrival of the next scheduled task. Otherwise, we extract the best task from the heap, add it to our result, and advance currentTime by its processing duration. This ensures that at every decision point, we make the optimal choice according to the problem's rules efficiently.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int[] getOrder(int[][] tasks) {6        int n = tasks.length;7        8        // Create an array of tasks with their original indices: [enqueueTime, processingTime, originalIndex]9        int[][] indexedTasks = new int[n][3];10        for (int i = 0; i < n; i++) {11            indexedTasks[i][0] = tasks[i][0];12            indexedTasks[i][1] = tasks[i][1];13            indexedTasks[i][2] = i;14        }15        16        // Sort tasks by enqueueTime17        Arrays.sort(indexedTasks, (a, b) -> Integer.compare(a[0], b[0]));18        19        // Min-heap to store available tasks: [processingTime, originalIndex]20        // Prioritize by processingTime, then by index21        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {22            if (a[0] != b[0]) {23                return Integer.compare(a[0], b[0]); // Shorter processing time first24            } else {25                return Integer.compare(a[1], b[1]); // Smaller index first for ties26            }27        });28        29        int[] result = new int[n];30        int resultIndex = 0;31        int taskIndex = 0;32        long currentTime = 0;33        34        while (resultIndex < n) {35            // Add all tasks that have become available by currentTime to the heap36            while (taskIndex < n && indexedTasks[taskIndex][0] <= currentTime) {37                pq.offer(new int[]{indexedTasks[taskIndex][1], indexedTasks[taskIndex][2]});38                taskIndex++;39            }40            41            // If the CPU is idle and no tasks are available, fast-forward time42            if (pq.isEmpty()) {43                currentTime = indexedTasks[taskIndex][0];44            } else { // Process the next task from the heap45                int[] nextTask = pq.poll();46                int processingTime = nextTask[0];47                int originalIndex = nextTask[1];48                49                result[resultIndex++] = originalIndex;50                currentTime += processingTime;51            }52        }53        54        return result;55    }56}

Complexity

Time

O(n log n). The initial sorting of the tasks takes O(n log n). The main loop processes each task once. Each task is pushed onto the heap (O(log n)) and popped from the heap (O(log n)) exactly once. Thus, the total time complexity is dominated by the sorting and heap operations.

Space

O(n). We need O(n) space for the `indexedTasks` array. The min-heap can, in the worst-case scenario, hold all `n` tasks (if they all become available at the same time). The `result` array also takes O(n) space.

Trade-offs

Pros

Highly efficient, with a time complexity of O(n log n).
Correctly and optimally solves the problem within the given constraints.
It's a standard and robust pattern for solving discrete-event simulation and scheduling problems.

Cons

Requires more memory due to the sorted copy of tasks and the heap.
Implementation is more complex than the brute-force approach.

Solutions

Solution

1class Solution { public int [] getOrder ( int [][] tasks ) { int n = tasks . length ; int [][] ts = new int [ n ][ 3 ]; for ( int i = 0 ; i < n ; ++ i ) { ts [ i ] = new int [] { tasks [ i ][ 0 ], tasks [ i ][ 1 ], i }; } Arrays . sort ( ts , ( a , b ) -> a [ 0 ] - b [ 0 ]); int [] ans = new int [ n ]; PriorityQueue < int []> q = new PriorityQueue <>(( a , b ) -> a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ]); int i = 0 , t = 0 , k = 0 ; while (! q . isEmpty () || i < n ) { if ( q . isEmpty ()) { t = Math . max ( t , ts [ i ][ 0 ]); } while ( i < n && ts [ i ][ 0 ] <= t ) { q . offer ( new int [] { ts [ i ][ 1 ], ts [ i ][ 2 ]}); ++ i ; } var p = q . poll (); ans [ k ++] = p [ 1 ]; t += p [ 0 ]; } return ans ; } }

1class Solution { public: vector < int > getOrder ( vector < vector < int >>& tasks ) { int n = 0 ; for ( auto & task : tasks ) task . push_back ( n ++ ); sort ( tasks . begin (), tasks . end ()); using pii = pair < int , int > ; priority_queue < pii , vector < pii > , greater < pii >> q ; int i = 0 ; long long t = 0 ; vector < int > ans ; while ( ! q . empty () || i < n ) { if ( q . empty ()) t = max ( t , ( long long ) tasks [ i ][ 0 ]); while ( i < n && tasks [ i ][ 0 ] <= t ) { q . push ({ tasks [ i ][ 1 ], tasks [ i ][ 2 ]}); ++ i ; } auto [ pt , j ] = q . top (); q . pop (); ans . push_back ( j ); t += pt ; } return ans ; } };

1class Solution : def getOrder ( self , tasks : List [ List [ int ]]) -> List [ int ]: for i , task in enumerate ( tasks ): task . append ( i ) tasks . sort () ans = [] q = [] n = len ( tasks ) i = t = 0 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 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem