Problem Description

You have n tasks numbered from 0 to n - 1. Each task is described by a 2D array tasks, where tasks[i] = [enqueueTime_i, processingTime_i]. This means:

• Task i becomes available at time enqueueTime_i
• Task i takes processingTime_i units of time to complete

You have a single-threaded CPU that processes tasks according to these rules:

1. When idle with no available tasks: The CPU stays idle and waits
2. When idle with available tasks: The CPU picks the task with the shortest processingTime. If there's a tie, it picks the task with the smallest index
3. During processing: Once a task starts, it runs to completion without interruption
4. After completion: The CPU can immediately start the next task

Your goal is to determine and return the order in which the CPU will process all tasks.

For example, if you have tasks [[1,2], [2,4], [3,2], [4,1]]:

• At time 1, task 0 becomes available and starts (no other choices)
• At time 3 (after task 0 finishes), tasks 1 and 2 are available. Task 2 has shorter processing time (2 vs 4), so it runs next
• At time 5, tasks 1 and 3 are available. Task 3 has shorter processing time (1 vs 4), so it runs next
• Finally, task 1 runs

The processing order would be [0, 2, 3, 1].

Intuition

The key insight is that this problem simulates a CPU scheduler that always picks the shortest job available. At any given moment, we need to know which tasks are available and quickly select the one with minimum processing time.

Think about what happens in real time: tasks become available at different times, and we can only consider tasks that have already "arrived" (their enqueueTime has passed). Among these available tasks, we want to efficiently find and extract the one with minimum processing time.

This naturally leads us to two important observations:

1. We need to process tasks in time order: We should look at tasks as they become available, which suggests sorting tasks by their enqueueTime. This way, we can iterate through tasks chronologically and add them to our available pool when the current time reaches their enqueueTime.

2. We need quick access to the minimum: Among available tasks, we repeatedly need to find and remove the one with shortest processing time. This is exactly what a min heap (priority queue) does efficiently - it maintains elements so we can always extract the minimum in O(log n) time.

The simulation flow becomes clear:

• Sort tasks by arrival time so we can process them chronologically
• Maintain current time t as we execute tasks
• Use a min heap to store available tasks (ordered by processing time)
• When the CPU is free, add all newly available tasks to the heap, then pick the shortest one
• Update the current time after each task completes
• If no tasks are available, jump forward in time to when the next task arrives

We need to track the original indices since the problem asks for the order of task indices, not the tasks themselves. This is why we append the original index to each task before sorting.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a simulation approach using sorting and a min heap:

1. Preprocessing - Add Original Indices:

for i, task in enumerate(tasks):
    task.append(i)

We append each task's original index to preserve it after sorting, transforming each task from [enqueueTime, processingTime] to [enqueueTime, processingTime, originalIndex].

2. Sort Tasks by Enqueue Time:

tasks.sort()

This ensures we can process tasks chronologically as they become available.

3. Initialize Variables:

• ans = []: Stores the order of task indices
• q = []: Min heap for available tasks
• i = 0: Pointer to track which tasks we've considered
• t = 0: Current time

4. Main Simulation Loop:

while q or i < n:

Continue while there are tasks in the heap or unprocessed tasks remaining.

5. Handle Idle Time:

if not q:
    t = max(t, tasks[i][0])

If the heap is empty (no available tasks), jump time forward to either the current time or the next task's enqueueTime, whichever is later.

6. Add Available Tasks to Heap:

while i < n and tasks[i][0] <= t:
    heappush(q, (tasks[i][1], tasks[i][2]))
    i += 1

Add all tasks whose enqueueTime is less than or equal to current time t to the min heap. The heap stores tuples (processingTime, originalIndex) so it naturally orders by processing time first, then by index if there's a tie.

7. Process Next Task:

pt, j = heappop(q)
ans.append(j)
t += pt

Extract the task with minimum processing time from the heap, add its index to the result, and advance time by the task's processing duration.

Time Complexity: O(n log n) - dominated by the initial sort and heap operations (each task is pushed and popped once).

Space Complexity: O(n) - for the heap and result array.

The beauty of this solution is how it naturally handles all edge cases: gaps in task availability, multiple tasks becoming available simultaneously, and the tie-breaking rule for tasks with equal processing times.

Example Walkthrough

Let's trace through the algorithm with tasks = [[1,2], [2,4], [3,2], [4,1]].

Step 1: Add original indices

• Task 0: [1,2] → [1,2,0]
• Task 1: [2,4] → [2,4,1]
• Task 2: [3,2] → [3,2,2]
• Task 3: [4,1] → [4,1,3]

Step 2: Sort by enqueue time After sorting: [[1,2,0], [2,4,1], [3,2,2], [4,1,3]] (already sorted in this case)

Step 3: Initialize

• ans = [], q = [] (min heap), i = 0, t = 0

Step 4: Main simulation

Iteration 1:

• Heap is empty, so t = max(0, tasks[0][0]) = 1
• Add tasks with enqueueTime ≤ 1: task [1,2,0]
• Heap: [(2,0)]
• Pop (2,0): process task 0
• ans = [0], t = 1 + 2 = 3

Iteration 2:

• Add tasks with enqueueTime ≤ 3: tasks [2,4,1] and [3,2,2]
• Heap: [(2,2), (4,1)] (ordered by processing time)
• Pop (2,2): process task 2
• ans = [0,2], t = 3 + 2 = 5

Iteration 3:

• Add tasks with enqueueTime ≤ 5: task [4,1,3]
• Heap: [(1,3), (4,1)]
• Pop (1,3): process task 3
• ans = [0,2,3], t = 5 + 1 = 6

Iteration 4:

• No new tasks to add (all processed)
• Heap: [(4,1)]
• Pop (4,1): process task 1
• ans = [0,2,3,1], t = 6 + 4 = 10

Final Result: [0, 2, 3, 1]

The CPU processes task 0 first (only option at time 1), then task 2 (shorter than task 1), then task 3 (shortest available), and finally task 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the number of tasks.

The time complexity breaks down as follows:

• Adding indices to tasks: O(n) - iterating through all tasks once
• Sorting tasks by enqueue time: O(n × log n) - standard comparison-based sorting
• Main while loop processes each task exactly once: O(n) iterations total
  • Each heappush operation: O(log n) in worst case
  • Each heappop operation: O(log n) in worst case
  • Total heap operations: n pushes and n pops = O(n × log n)
• Overall: O(n) + O(n × log n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The space complexity consists of:

• Modified tasks list with added indices: O(n) - stores all tasks with their original indices
• Priority queue q: O(n) in worst case - can contain all tasks if they all have the same enqueue time
• Answer list ans: O(n) - stores indices of all tasks
• Other variables (i, t, pt, j): O(1)
• Overall: O(n) + O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Time Values

One critical pitfall is that time values can accumulate to very large numbers. If enqueueTime and processingTime values are near their maximum (up to 10^9 according to typical constraints), the cumulative time can exceed standard integer limits in some languages.

Problem Example:

tasks = [[1000000000, 1000000000], [1, 1000000000]]
# After processing task 0, current_time becomes 2000000000
# This could cause overflow in languages with fixed integer sizes

Solution: In Python, integers have arbitrary precision so overflow isn't an issue. However, in other languages like Java or C++, use long instead of int:

long currentTime = 0;  // Use long instead of int

2. Modifying Input Array In-Place

The code modifies the input tasks array by appending indices to it. This can cause issues if:

• The input needs to be preserved for other operations
• The function is called multiple times with the same input
• Testing/debugging becomes harder with mutated inputs

Problem Example:

solution = Solution()
tasks = [[1,2], [2,4]]
result1 = solution.getOrder(tasks)  # tasks is now [[1,2,0], [2,4,1]]
result2 = solution.getOrder(tasks)  # Error! tasks already has indices appended

Solution: Create a new list instead of modifying the input:

def getOrder(self, tasks: List[List[int]]) -> List[int]:
    # Create a new list with indices instead of modifying input
    indexed_tasks = [[task[0], task[1], i] for i, task in enumerate(tasks)]
    indexed_tasks.sort()
    # ... rest of the code uses indexed_tasks instead of tasks

3. Incorrect Heap Priority for Tie-Breaking

When using a heap with tuples, Python compares elements lexicographically. If only pushing (processingTime, index) without careful consideration, the tie-breaking might work correctly by accident. However, relying on implicit behavior can lead to bugs if the data structure changes.

Problem Example: If someone mistakenly pushes (processingTime, enqueueTime, index) thinking more information is better:

# Wrong! This would break tie by enqueueTime instead of index
heapq.heappush(available_tasks, (tasks[i][1], tasks[i][0], tasks[i][2]))

Solution: Be explicit about what goes into the heap and document why:

# Heap stores exactly (processing_time, original_index)
# This ensures: 1) Primary sort by processing_time
#              2) Secondary sort by index (for ties)
heapq.heappush(available_tasks, (tasks[task_index][1], tasks[task_index][2]))

4. Not Handling Empty Task List

While the problem typically guarantees n >= 1, defensive programming suggests handling edge cases.

Problem Example:

tasks = []
# The code would work but it's good practice to handle explicitly

Solution: Add an early return for empty input:

def getOrder(self, tasks: List[List[int]]) -> List[int]:
    if not tasks:
        return []
    # ... rest of the code