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).
  3. Start processing tasks:
    • 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:
10  vector<int> getOrder(vector<vector<int>>& tasks) {
11    int n = tasks.size();
12
13    // Add index information.
14    for (int i = 0; i < n; ++i)
15      tasks[i].push_back(i);
16
17    // Sort tasks by their enqueueTime.
18    sort(tasks.begin(), tasks.end());
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())
28        time = max(time, static_cast<long>(tasks[i][0]));
29      
30      // Add all tasks with enqueueTime <= time to minHeap
31      while (i < n && time >= tasks[i][0]) {
32        minHeap.emplace(tasks[i][1], tasks[i][2]);
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]:
6        n = len(tasks)
7        
8        # Add index information.
9        for i in range(n):
10            tasks[i].append(i)
11        
12        # Sort tasks by their enqueueTime.
13        tasks.sort()
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:
23                time = max(time, tasks[i][0])
24            
25            # Add all tasks with enqueueTime <= time to min_heap
26            while i < n and time >= tasks[i][0]:
27                heapq.heappush(min_heap, (tasks[i][1], tasks[i][2]))
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[0] || (p === value[0] && idx > value[1]));
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
24function getOrder(tasks) {
25  const n = tasks.length;
26
27  // Add index information.
28  tasks.forEach((task, idx) => task.push(idx));
29
30  // Sort tasks by their enqueueTime.
31  tasks.sort((a, b) => a[0] - b[0]);
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())
41      time = Math.max(time, tasks[i][0]);
42
43    // Add all tasks with enqueueTime <= time to minHeap
44    while (i < n && time >= tasks[i][0]) {
45      minHeap.push([tasks[i][1], tasks[i][2]]);
46      i += 1;
47    }
48
49    // Process the task with the smallest processingTime from minHeap
50    const [procTime, index] = minHeap.pop();
51    time += procTime;
52    ans.push(index);
53  }
54
55  return ans;
56}