Single-Threaded CPU Problem

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.

Solution

Method 1 – Sort and Min-Heap

Intuition

To always assign the CPU the shortest available task, we use a min-heap (priority queue) to efficiently select the task with the smallest processing time. However, since some short tasks may only become available later, we must first sort all tasks by their enqueue (start) time and only add them to the heap when they are available. This ensures the CPU never waits unnecessarily and always processes the optimal task.

Approach

  1. Preprocess Tasks:
    • Attach the original index to each task for result tracking.
    • Sort all tasks by their enqueue time.
  2. Simulate CPU Scheduling:
    • Use a min-heap to store available tasks, ordered by processing time (and index for ties).
    • Track the current time and iterate through the sorted tasks:
      • Add all tasks whose enqueue time is less than or equal to the current time to the heap.
      • If the heap is empty, fast-forward time to the next task’s enqueue time.
      • Otherwise, pop the task with the shortest processing time from the heap, process it, and update the current time.
    • Repeat until all tasks are processed.
  3. Build the Result:
    • Record the order in which tasks are processed using their original indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
	vector<int> getOrder(vector<vector<int>>& tasks) {
		int n = tasks.size();
		vector<array<int, 3>> arr;
		for (int i = 0; i < n; ++i) arr.push_back({tasks[i][0], tasks[i][1], i});
		sort(arr.begin(), arr.end());
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
		vector<int> ans;
		long long time = 0;
		int i = 0;
		while (i < n || !pq.empty()) {
			if (pq.empty() && time < arr[i][0]) time = arr[i][0];
			while (i < n && arr[i][0] <= time) {
				pq.push({arr[i][1], arr[i][2]});
				++i;
			}
			if (!pq.empty()) {
				auto [pt, idx] = pq.top(); pq.pop();
				ans.push_back(idx);
				time += pt;
			}
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import "container/heap"
type Task struct{ enqueue, process, idx int }
type MinHeap []Task
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if h[i].process == h[j].process {
		return h[i].idx < h[j].idx
	}
	return h[i].process < h[j].process
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Task)) }
func (h *MinHeap) Pop() interface{} {
	n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x
}
func getOrder(tasks [][]int) []int {
	n := len(tasks)
	arr := make([]Task, n)
	for i := 0; i < n; i++ {
		arr[i] = Task{tasks[i][0], tasks[i][1], i}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i].enqueue < arr[j].enqueue })
	h := &MinHeap{}
	heap.Init(h)
	ans := []int{}
	time, i := 0, 0
	for i < n || h.Len() > 0 {
		if h.Len() == 0 && time < arr[i].enqueue {
			time = arr[i].enqueue
		}
		for i < n && arr[i].enqueue <= time {
			heap.Push(h, arr[i])
			i++
		}
		if h.Len() > 0 {
			t := heap.Pop(h).(Task)
			ans = append(ans, t.idx)
			time += t.process
		}
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
	public int[] getOrder(int[][] tasks) {
		int n = tasks.length;
		int[][] arr = new int[n][3];
		for (int i = 0; i < n; i++) {
			arr[i][0] = tasks[i][0];
			arr[i][1] = tasks[i][1];
			arr[i][2] = i;
		}
		Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);
		int[] ans = new int[n];
		int idx = 0, i = 0;
		long time = 0;
		while (i < n || !pq.isEmpty()) {
			if (pq.isEmpty() && time < arr[i][0]) time = arr[i][0];
			while (i < n && arr[i][0] <= time) pq.offer(arr[i++]);
			if (!pq.isEmpty()) {
				int[] t = pq.poll();
				ans[idx++] = t[2];
				time += t[1];
			}
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
	fun getOrder(tasks: Array<IntArray>): IntArray {
		val n = tasks.size
		val arr = Array(n) { i -> intArrayOf(tasks[i][0], tasks[i][1], i) }
		arr.sortBy { it[0] }
		val pq = java.util.PriorityQueue<IntArray> { a, b ->
			if (a[1] == b[1]) a[2] - b[2] else a[1] - b[1]
		}
		val ans = IntArray(n)
		var idx = 0
		var i = 0
		var time = 0L
		while (i < n || pq.isNotEmpty()) {
			if (pq.isEmpty() && time < arr[i][0]) time = arr[i][0].toLong()
			while (i < n && arr[i][0] <= time) pq.add(arr[i++])
			if (pq.isNotEmpty()) {
				val t = pq.poll()
				ans[idx++] = t[2]
				time += t[1]
			}
		}
		return ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import heapq
class Solution:
	def getOrder(self, tasks: list[list[int]]) -> list[int]:
		n = len(tasks)
		arr = sorted([(et, pt, i) for i, (et, pt) in enumerate(tasks)])
		ans = []
		h = []
		time = i = 0
		while i < n or h:
			if not h and time < arr[i][0]:
				time = arr[i][0]
			while i < n and arr[i][0] <= time:
				heapq.heappush(h, (arr[i][1], arr[i][2]))
				i += 1
			if h:
				pt, idx = heapq.heappop(h)
				ans.append(idx)
				time += pt
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
	pub fn get_order(tasks: Vec<Vec<i32>>) -> Vec<i32> {
		let n = tasks.len();
		let mut arr: Vec<(i32, i32, usize)> = tasks.iter().enumerate().map(|(i, t)| (t[0], t[1], i)).collect();
		arr.sort();
		let mut ans = Vec::with_capacity(n);
		let mut h = BinaryHeap::new();
		let mut time = 0;
		let mut i = 0;
		while i < n || !h.is_empty() {
			if h.is_empty() && time < arr[i].0 { time = arr[i].0; }
			while i < n && arr[i].0 <= time {
				h.push(Reverse((arr[i].1, arr[i].2)));
				i += 1;
			}
			if let Some(Reverse((pt, idx))) = h.pop() {
				ans.push(idx as i32);
				time += pt;
			}
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function getOrder(tasks: number[][]): number[] {
	const n = tasks.length;
	const arr = tasks.map((t, i) => [t[0], t[1], i]);
	arr.sort((a, b) => a[0] - b[0]);
	const h: [number, number][] = [];
	const ans: number[] = [];
	let time = 0, i = 0;
	while (i < n || h.length) {
		if (!h.length && time < arr[i][0]) time = arr[i][0];
		while (i < n && arr[i][0] <= time) {
			h.push([arr[i][1], arr[i][2]]);
			i++;
		}
		if (h.length) {
			h.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
			const [pt, idx] = h.shift()!;
			ans.push(idx);
			time += pt;
		}
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n log n), since we sort the tasks and use heap operations for each task.
  • 🧺 Space complexity: O(n), for storing the tasks and the heap.
Rust Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

pub fn get_order(tasks: Vec<Vec<i32>>) -> Vec<i32> {
	let mut tasks_ = vec![];
	let n = tasks.len();
	for i in 0 .. n {
		tasks_.push((tasks[i][0], tasks[i][1], i));
	}
	tasks_.sort();

	let mut i = 0;
	let mut minHeap = BinaryHeap::new();
	let mut ans = vec![];
	let mut t = 0;
	while i < n || !minHeap.is_empty() {
		if minHeap.is_empty() {
			t = t.max(tasks_[i].0);
		}
		while i < n && tasks_[i].0 <= t {
			minHeap.push(Reverse((tasks_[i].1, tasks_[i].2)));
			i += 1;
		}
		if let Some(Reverse((processing_time, idx))) = minHeap.pop() {
			ans.push(idx as i32);
			t += processing_time;
		} 
	}
	return ans;
}