Single Threaded CPU

Problem Description

You are given n tasks where tasks[i] = [enqueueTimei, processingTimei]. The CPU picks the available task with the shortest processing time (ties broken by original index). Return the order in which tasks are processed.

Examples

Constraints

• 1 ≤ tasks.length ≤ 10⁵
• 1 ≤ enqueueTimei, processingTimei ≤ 10⁹

Simulate the CPU with a Min-Heap

Sort tasks by enqueue time (retaining original index). Simulate the clock: at each moment, add all tasks that have become available to a min-heap sorted by (processing time, original index). Pick the top, run it to completion, advance the clock by processing time, then add newly available tasks.

If the heap is empty when the CPU finishes a task, jump the clock forward to the next task’s enqueue time rather than waiting one unit at a time.

Solution: Sorted Tasks + Min-Heap Simulation

import java.util.*;

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        // pair tasks with their original index, then sort by enqueue time
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> tasks[a][0] - tasks[b][0]);

        // min-heap: [processingTime, originalIndex]
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
        );

        int[] result = new int[n];
        long time = 0;
        int taskIdx = 0, resultIdx = 0;

        while (resultIdx < n) {
            // add all tasks available by current time
            while (taskIdx < n && tasks[indices[taskIdx]][0] <= time) {
                int oi = indices[taskIdx];
                heap.offer(new int[]{tasks[oi][1], oi});
                taskIdx++;
            }

            if (heap.isEmpty()) {
                // CPU idle: jump to next task's enqueue time
                time = tasks[indices[taskIdx]][0];
                continue;
            }

            int[] top = heap.poll();
            result[resultIdx++] = top[1];
            time += top[0]; // advance clock by processing time
        }
        return result;
    }
}

import heapq

class Solution:
    def getOrder(self, tasks: list[list[int]]) -> list[int]:
        # attach original index, sort by enqueue time
        indexed = sorted(enumerate(tasks), key=lambda x: x[1][0])

        heap = []  # (processing_time, original_index)
        result = []
        time = 0
        i = 0

        while len(result) < len(tasks):
            # add all tasks available at current time
            while i < len(indexed) and indexed[i][1][0] <= time:
                orig_idx, (enqueue, process) = indexed[i]
                heapq.heappush(heap, (process, orig_idx))
                i += 1

            if not heap:
                # CPU idle: jump to next task's enqueue time
                time = indexed[i][1][0]
                continue

            process_time, orig_idx = heapq.heappop(heap)
            result.append(orig_idx)
            time += process_time

        return result

#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>

class Solution {
public:
    std::vector<int> getOrder(std::vector<std::vector<int>>& tasks) {
        int n = tasks.size();
        std::vector<int> indices(n);
        std::iota(indices.begin(), indices.end(), 0);
        std::sort(indices.begin(), indices.end(), [&](int a, int b) {
            return tasks[a][0] < tasks[b][0];
        });

        // min-heap: {processingTime, originalIndex}
        using T = std::pair<long long, int>;
        std::priority_queue<T, std::vector<T>, std::greater<T>> heap;

        std::vector<int> result;
        long long time = 0;
        int taskIdx = 0;

        while ((int)result.size() < n) {
            while (taskIdx < n && tasks[indices[taskIdx]][0] <= time) {
                int oi = indices[taskIdx++];
                heap.push({tasks[oi][1], oi});
            }

            if (heap.empty()) {
                time = tasks[indices[taskIdx]][0];
                continue;
            }

            auto [pt, oi] = heap.top(); heap.pop();
            result.push_back(oi);
            time += pt;
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). Sorting takes O(n log n). Each task is pushed and popped from the heap once, each O(log n).
• Space Complexity: O(n) for the heap and indices array.

Where it breaks: use long long (or int64) for the clock. Enqueue times and processing times can each be up to 10⁹, and you sum them over up to 10⁵ tasks. The total time can reach 10¹⁴, overflowing a 32-bit integer.

Common Mistakes

• Not advancing the clock to the next enqueue time when the heap is empty. Incrementing by 1 works but takes O(next_enqueue_time) iterations of the outer loop, which is unacceptably slow.
• Using int for the time variable. Integer overflow silently corrupts the simulation.
• Not preserving the original task index after sorting. After sorting by enqueue time, you lose the original order. Always carry the original index along.

Frequently Asked Questions

Why sort by enqueue time first? Tasks only become available at their enqueue time. Sorting lets you efficiently find which tasks have become available using a pointer that advances with time, rather than scanning all tasks on every step.

What does “same processing time” mean for the tie-breaking rule? When two available tasks have equal processing time, the CPU picks the one with the smaller original (0-indexed) task label. The (processingTime, originalIndex) tuple in the heap handles this automatically.

← All Problems