This problem simulates a CPU scheduler. We have a set of tasks, each arriving at a specific time and taking a specific duration. The CPU is single-threaded, so it handles one task at a time. When it finishes a task (or starts idle), it picks the next task from all currently available tasks using a specific priority: shortest processing time first, and if there's a tie, the smaller original index wins.

The tricky part is that tasks arrive at different times. While the CPU is busy processing one task, new tasks may become available. So we can't just sort by processing time and call it a day. We need to track which tasks are available at each decision point, and those decision points change dynamically based on what the CPU is doing.

The key observation: at each moment the CPU finishes a task, we need to efficiently find the available task with the smallest processing time (and smallest index as a tiebreaker). This screams for a min-heap (priority queue).

Key Constraints:

Intuition

The most direct approach: simulate the CPU's behavior step by step. At each decision point (when the CPU becomes idle), scan through all tasks to find which ones are available, then pick the one with the shortest processing time and smallest index among those.

This is what you'd naturally think of first. The CPU finishes a task, so we look at every task, check if its enqueue time has passed, skip any already-processed tasks, and pick the best candidate from the remaining ones.

Algorithm

a. Scan all tasks to find available ones (enqueue time <= current time and not yet processed).

b. Among available tasks, pick the one with the smallest processing time (ties broken by index).

c. If no tasks are available, jump the current time forward to the earliest unprocessed task's enqueue time.

d. Add the chosen task to the result. Advance current time by its processing time.

Example Walkthrough

Code

Every time the CPU becomes idle, we scan all n tasks to find the best one. What if we sorted tasks by arrival time and used a min-heap to always know the shortest available task?

Intuition

The brute force does two things inefficiently: finding available tasks and picking the best one. We can fix both with a two-step strategy.

First, sort the tasks by enqueue time. This way, we can process arrivals in order using a simple pointer. Instead of scanning all tasks to check availability, we just advance the pointer until we've added all tasks that have arrived by the current time.

Second, use a min-heap (priority queue) to hold the available tasks. The heap is ordered by (processing time, original index), so extracting the minimum always gives us the correct next task according to the CPU's scheduling rules.

Here's the flow: when the CPU finishes a task, advance the current time, push any newly arrived tasks into the heap, then pop the top element. If the heap is empty but tasks remain, jump forward in time to the next arrival.

Algorithm

a. Push all tasks with enqueueTime <= currentTime into the heap.

b. If the heap is empty, jump currentTime to the next task's enqueueTime, then push that task (and any others arriving at the same time).

c. Pop the task with the smallest (processingTime, originalIndex) from the heap.

d. Add its original index to the result. Advance currentTime by its processing time.

Example Walkthrough

Code