Practice/DoorDash/Leetcode 1834. Single-Threaded CPU

Leetcode 1834. Single-Threaded CPU

CodingOptional

Problem

You are simulating a single-threaded CPU that processes tasks. Each task is represented by two values: the time at which it becomes available for processing, and how long it takes to complete once started.

The CPU follows these rules:

• It can only process one task at a time
• Once a task begins execution, it runs to completion without interruption
• When the CPU is idle, it selects from all available tasks the one with the shortest processing time
• If multiple tasks have the same processing time, it chooses the one with the smallest original index
• If no tasks are available, the CPU waits until the next task becomes available

Given an array of tasks where tasks[i] = [enqueueTime, processingTime], return an array representing the order in which the CPU will process the tasks (using their original indices).

Requirements

1. Return an array of task indices in the order they are processed by the CPU
2. Always select the available task with the minimum processing time
3. Break ties by choosing the task with the smaller index
4. Handle cases where the CPU must wait for tasks to become available

Constraints

• 1 ≤ tasks.length ≤ 100,000
• 1 ≤ enqueueTime, processingTime ≤ 1,000,000,000
• All task indices are unique

Examples

Example 1:

` Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1] Explanation:

• At time 1: Task 0 is available and starts processing (completes at time 3)
• At time 2: Task 1 becomes available (waiting)
• At time 3: Tasks 1, 2, 3 are available. Task 2 has processing time 2 (same as task 3), but lower index, so task 2 is selected (completes at time 5)
• At time 5: Tasks 1 and 3 are available. Task 3 has processing time 1 < 4, so task 3 is selected (completes at time 6)
• At time 6: Only task 1 remains, processes from time 6 to 10 `

Example 2:

Input: tasks = [[1,5],[1,3],[1,4]] Output: [1,2,0] Explanation: All tasks become available at time 1. They are processed in order of processing time: task 1 (3), task 2 (4), task 0 (5).

Example 3:

Input: tasks = [[5,3],[10,2]] Output: [0,1] Explanation: Task 0 processes from 5 to 8. At time 8, only task 1 is available (became available at time 10 > 8), so CPU waits until time 10 and processes task 1.