Single Threaded CPU

Difficulty: Medium Source: NeetCode

Problem

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the ith task will be available to process at enqueueTime_i and will take processingTime_i units of time 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 waits until the next task becomes available.
• If the CPU is idle and there are available tasks, the CPU picks the task with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.

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]

Example 2: Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] Output: [4, 3, 2, 0, 1]

Constraints:

• tasks.length == n
• 1 <= n <= 10^5
• 1 <= enqueueTime_i, processingTime_i <= 10^9

Prerequisites

Before attempting this problem, you should be comfortable with:

• Simulation — stepping through a process with explicit time tracking
• Min-heap — extracting the task with the shortest processing time
• Sorting — sorting tasks by enqueue time while preserving original indices

1. Brute Force — Simulate with Linear Scan

Intuition

At each CPU step, find all tasks that have arrived so far, pick the one with the shortest processing time (tie-break by original index), run it, advance time by its processing time, and repeat. The inner scan is O(n) and we do it n times.

Algorithm

1. Tag each task with its original index: (enqueueTime, processingTime, index).
2. Sort by enqueue time.
3. Maintain time (current CPU time) and a list of completed task indices.
4. While tasks remain: find all arrived tasks, pick the best one, advance time, record it.

Solution

def getOrder(tasks):
    # Attach original indices
    indexed = sorted(enumerate(tasks), key=lambda x: x[1][0])
    n = len(tasks)
    result = []
    time = 0
    i = 0  # pointer into sorted indexed list

    while len(result) < n:
        # Collect all tasks available at current time
        available = []
        while i < n and indexed[i][1][0] <= time:
            orig_idx, (eq, pt) = indexed[i]
            available.append((pt, orig_idx))
            i += 1

        if available:
            available.sort()
            pt, orig_idx = available[0]
            result.append(orig_idx)
            time += pt
            # Put back unused tasks (brute force: re-scan next iteration)
            # For simplicity, use a remaining list approach
        else:
            # CPU idle — jump to next task's enqueue time
            if i < n:
                time = indexed[i][1][0]

    return result


# This brute force version is simplified; for correctness with "put back",
# use the heap approach below.
print(getOrder([[7,10],[7,12],[7,5],[7,4],[7,2]]))  # [4,3,2,0,1]

Complexity

• Time: O(n²) — linear scan per task
• Space: O(n)

2. Min-Heap Simulation

Intuition

Sort tasks by enqueue time (keeping original indices). Maintain a min-heap of (processingTime, originalIndex) for tasks that have already arrived. At each step, push all newly available tasks onto the heap, then pop the best one (shortest time, then smallest index). If the heap is empty, jump the clock forward to the next task’s enqueue time.

Algorithm

1. Create sorted_tasks = sorted(enumerate(tasks), key=lambda x: x[1][0]) — sorted by enqueue time, preserving original index.
2. Initialize time = 0, heap = [], i = 0, result = [].
3. While result has fewer than n items: a. Push all tasks with enqueueTime <= time onto the heap as (processingTime, originalIndex). b. If heap is empty, jump time to the next task’s enqueue time and continue. c. Pop (pt, orig_idx) from the heap, append orig_idx to result, advance time += pt.
4. Return result.

Solution

import heapq

def getOrder(tasks):
    # (enqueueTime, processingTime, originalIndex)
    sorted_tasks = sorted(
        [(eq, pt, i) for i, (eq, pt) in enumerate(tasks)],
        key=lambda x: x[0]
    )
    n = len(tasks)
    result = []
    heap = []  # (processingTime, originalIndex)
    time = 0
    i = 0

    while len(result) < n:
        # Enqueue all tasks that have arrived by current time
        while i < n and sorted_tasks[i][0] <= time:
            eq, pt, orig = sorted_tasks[i]
            heapq.heappush(heap, (pt, orig))
            i += 1

        if heap:
            pt, orig = heapq.heappop(heap)
            result.append(orig)
            time += pt
        else:
            # CPU idle — jump to next task's arrival
            time = sorted_tasks[i][0]

    return result


print(getOrder([[1,2],[2,4],[3,2],[4,1]]))          # [0, 2, 3, 1]
print(getOrder([[7,10],[7,12],[7,5],[7,4],[7,2]]))  # [4, 3, 2, 0, 1]
print(getOrder([[1,1],[2,2],[4,3]]))                 # [0, 1, 2]

Complexity

• Time: O(n log n) — sort plus n heap operations
• Space: O(n)

Common Pitfalls

Not preserving original indices after sorting. You sort tasks by enqueue time to know what’s available, but the output wants original indices. Always track (enqueueTime, processingTime, originalIndex) together.

Forgetting the CPU idle jump. When the heap is empty (no task has arrived yet), don’t increment time by 1 — jump directly to the next task’s enqueue time. Incrementing by 1 works but gives TLE for large inputs with big gaps.

Tie-breaking order. Python’s heap is lexicographic on tuples, so (processingTime, originalIndex) automatically breaks ties by smaller index first — exactly what the problem requires. Make sure your tuple has this order.