Problem · Heap
Single-Threaded CPU
Learn this problem● Medium
RobloxFULLTIMEPHONE SCREEN
See Roblox hiring insightsRobloxFULLTIMEPHONE SCREENProblem statement
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 i-th task becomes available to process at enqueueTime_i and takes processingTime_i to finish.
You have a single-threaded CPU that can process at most one task at a time and acts as follows:
- 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 chooses the one with the shortest processing time. If multiple available tasks have the same shortest processing time, it chooses the task with the smallest index.
- Once a task is started, the CPU processes the entire task without stopping.
- The CPU can finish a task and then start a new one instantly.
Return the order in which the CPU processes the tasks.
The standard approach sorts the tasks by enqueue time, advances a current time, and keeps a min-heap of currently-available tasks keyed by (processingTime, originalIndex). When the heap is empty but tasks remain, jump the clock forward to the next enqueue time.
Function
getOrder(tasks: int[][]) → int[]Examples
Example 1
tasks = [[1, 2], [2, 4], [3, 2], [4, 1]]return = [0, 2, 3, 1]The CPU starts at t=1 with task 0 (length 2). At t=3, tasks 1 and 2 are ready; task 2 wins (length 2 vs 4). At t=5 only task 3 remains and runs (length 1). At t=6 task 1 runs (length 4).
Example 2
tasks = [[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]return = [4, 3, 2, 0, 1]All tasks arrive at t=7. The CPU drains them by shortest processing time, breaking ties by smallest index: task 4 (2), task 3 (4), task 2 (5), task 0 (10), task 1 (12).
Constraints
1 <= tasks.length <= 10^5tasks[i].length == 21 <= enqueueTime_i, processingTime_i <= 10^9