# Single-Threaded CPU
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/single-threaded-cpu)
Canonical: https://scaleengineer.com/dsa/problems/single-threaded-cpu
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
You are given `n`​​​​​​ tasks labeled from `0` to `n - 1` represented by a 2D integer array `tasks`, where `tasks[i] = [enqueueTimei, processingTimei]` means that the `i​​​​​​th`​​​​ task will be available to process at `enqueueTimei` and will take `processingTimei` to 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 <= 105`
* `1 <= enqueueTimei, processingTimei <= 109`

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[] result = new int[n];
        boolean[] processed = new boolean[n];
        long currentTime = 1;
        int resultIndex = 0;

        while (resultIndex < n) {
            int bestTaskIndex = -1;
            long minProcessingTime = Long.MAX_VALUE;
            
            // Find the best available task at the current time
            for (int i = 0; i < n; i++) {
                if (!processed[i] && tasks[i][0] <= currentTime) {
                    if (tasks[i][1] < minProcessingTime) {
                        minProcessingTime = tasks[i][1];
                        bestTaskIndex = i;
                    } else if (tasks[i][1] == minProcessingTime) {
                        if (i < bestTaskIndex) {
                            bestTaskIndex = i;
                        }
                    }
                }
            }

            // If no task is available, CPU is idle. Fast-forward time.
            if (bestTaskIndex == -1) {
                long nextEnqueueTime = Long.MAX_VALUE;
                for (int i = 0; i < n; i++) {
                    if (!processed[i]) {
                        nextEnqueueTime = Math.min(nextEnqueueTime, tasks[i][0]);
                    }
                }
                currentTime = nextEnqueueTime;
            } else { // Process the best task found
                result[resultIndex++] = bestTaskIndex;
                processed[bestTaskIndex] = true;
                currentTime += tasks[bestTaskIndex][1];
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize `currentTime = 0`, a boolean array `processed` of size `n` to track completed tasks, and an integer array `result` to store the output.
2. Loop `n` times, as we need to select `n` tasks in total.
3. 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`.
4. **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.
5. **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.
6. Once the best task (say, index `j`) is identified, add `j` to the `result` array.
7. Mark task `j` as processed by setting `processed[j] = true`.
8. Update `currentTime` by adding the `processingTime` of task `j` to it.
9. Repeat the loop until `n` tasks have been added to the `result` array.

## Sorting with a Min-Heap (Priority Queue)
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        
        // Create an array of tasks with their original indices: [enqueueTime, processingTime, originalIndex]
        int[][] indexedTasks = new int[n][3];
        for (int i = 0; i < n; i++) {
            indexedTasks[i][0] = tasks[i][0];
            indexedTasks[i][1] = tasks[i][1];
            indexedTasks[i][2] = i;
        }
        
        // Sort tasks by enqueueTime
        Arrays.sort(indexedTasks, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Min-heap to store available tasks: [processingTime, originalIndex]
        // Prioritize by processingTime, then by index
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]); // Shorter processing time first
            } else {
                return Integer.compare(a[1], b[1]); // Smaller index first for ties
            }
        });
        
        int[] result = new int[n];
        int resultIndex = 0;
        int taskIndex = 0;
        long currentTime = 0;
        
        while (resultIndex < n) {
            // Add all tasks that have become available by currentTime to the heap
            while (taskIndex < n && indexedTasks[taskIndex][0] <= currentTime) {
                pq.offer(new int[]{indexedTasks[taskIndex][1], indexedTasks[taskIndex][2]});
                taskIndex++;
            }
            
            // If the CPU is idle and no tasks are available, fast-forward time
            if (pq.isEmpty()) {
                currentTime = indexedTasks[taskIndex][0];
            } else { // Process the next task from the heap
                int[] nextTask = pq.poll();
                int processingTime = nextTask[0];
                int originalIndex = nextTask[1];
                
                result[resultIndex++] = originalIndex;
                currentTime += processingTime;
            }
        }
        
        return result;
    }
}
```
### Algorithm
1. **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.
2. **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.
3. **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`.
4. **Return Result:** Once the loop completes, the `result` array contains the correct processing order.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```