 # Leetcode 1834. Single-Threaded CPU Solution

## Problem Description:

In this problem, we are given `n` tasks represented by a 2D integer array `tasks`, where `tasks[i] = [enqueueTimei, processingTimei]`. This means that the `i-th` task will be available for processing at `enqueueTimei` and will take `processingTimei` to finish. We have a single-threaded CPU that can process at most one task at a time, and it follows the below rules:

1. If the CPU is idle and there are no available tasks to process, the CPU remains idle.
2. 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.
3. Once a task is started, the CPU will process the entire task without stopping.
4. The CPU can finish a task then start a new one instantly.

We need to return the order in which the CPU will process the tasks.

## Walkthrough

Suppose we have input tasks: `[[1, 2], [2, 4], [3, 2], [4, 1]]`. Let's walk through the algorithm step by step.

1. Sort the tasks by their `enqueueTime`. Our tasks array becomes `[[1, 2, 0], [2, 4, 1], [3, 2, 2], [4, 1, 3]]`, where the third element in each subarray is the task's original index.
2. Initialize an empty priority queue `minHeap` which sorts tasks by `processingTime`. Then initialize variables `i = 0` (task pointer) and `time = 0` (current time).
• As `minHeap` is empty, we set the `time` to the first task's `enqueueTime` (1).
• Now, we loop through the tasks and add all tasks whose `enqueueTime` is less than or equal to `time` into `minHeap`. In our example, task 0 and task 1 both meet this condition and are added to `minHeap`.
• Pop the task with the smallest `processingTime` from `minHeap`, and process it completely. Update the CPU's time accordingly. In our case, task 0 is popped and processed, making CPU's `time` equal to 3.
• Add tasks into `minHeap` again, which have an `enqueueTime` less than or equal to the updated `time`. In our case, task 2 is added.
• Again, process the task with the smallest `processingTime` from `minHeap`. Task 2 is processed, and the CPU's `time` becomes 5.
• Add tasks into `minHeap` again. Task 3 is added.
• Process task 3, making time 6.
• Process task 1, making time 10.
4. With no more tasks in `minHeap`, our final order is `[0, 2, 3, 1]`.

## Solution

### C++

``````1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <utility>
5
6using namespace std;
7
8class Solution {
9 public:
12
14    for (int i = 0; i < n; ++i)
16
17    // Sort tasks by their enqueueTime.
19
20    vector<int> ans;
21    // Create a minHeap that sorts tasks by processingTime.
22    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
23    int i = 0;      // Task pointer
24    long time = 0;  // Current time
25
26    while (i < n || !minHeap.empty()) {
27      if (minHeap.empty())
29
31      while (i < n && time >= tasks[i]) {
33        ++i;
34      }
35
36      // Process the task with the smallest processingTime from minHeap
37      const auto [procTime, index] = minHeap.top();
38      minHeap.pop();
39      time += procTime;
40      ans.push_back(index);
41    }
42
43    return ans;
44  }
45};``````

### Python

``````1from typing import List
2import heapq
3
4class Solution:
5    def getOrder(self, tasks: List[List[int]]) -> List[int]:
7
9        for i in range(n):
11
12        # Sort tasks by their enqueueTime.
14
15        ans = []
16        # Create a minHeap that sorts tasks by processingTime.
17        min_heap = []
18        i = 0  # Task pointer
19        time = 0  # Current time
20
21        while i < n or min_heap:
22            if not min_heap:
24
26            while i < n and time >= tasks[i]:
28                i += 1
29
30            # Process the task with the smallest processingTime from min_heap
31            proc_time, index = heapq.heappop(min_heap)
32            time += proc_time
33            ans.append(index)
34
35        return ans``````

### JavaScript

``````1class PriorityQueue {
2  constructor() {
3    this.queue = [];
4  }
5
6  push(value) {
7    let i = this.queue.findIndex(([p, idx]) => p > value || (p === value && idx > value));
8    if (i === -1) {
9      this.queue.push(value);
10    } else {
11      this.queue.splice(i, 0, value);
12    }
13  }
14
15  pop() {
16    return this.queue.shift();
17  }
18
19  empty() {
20    return this.queue.length === 0;
21  }
22}
23
26
29
30  // Sort tasks by their enqueueTime.
31  tasks.sort((a, b) => a - b);
32
33  const ans = [];
34  // Create a minHeap that sorts tasks by processingTime.
35  const minHeap = new PriorityQueue();
36  let i = 0; // Task pointer
37  let time = 0; // Current time
38
39  while (i < n || !minHeap.empty()) {
40    if (minHeap.empty())
42