LeetCode Solutions Blog

Single-Threaded CPU

Number: 1962

Difficulty: Medium

Paid? No

Problem Description

You are given n tasks labeled from 0 to n-1, where each task is represented as [enqueueTime, processingTime]. When a task becomes available at its enqueueTime, it can be processed by a single-threaded CPU. The CPU always selects the available task with the shortest processing time (or the smallest index if tied) and runs it to completion. If no tasks are available, the CPU remains idle until a task can be processed. Return the order in which the CPU executes the tasks.

Key Insights

Sort tasks by enqueueTime while preserving original indices.
Use a min-heap (priority queue) to efficiently choose the task with the shortest processing time.
If the heap is empty and tasks are yet to arrive, jump the current time to the next task's enqueueTime.
Process tasks until all tasks have been scheduled.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and heap operations. Space Complexity: O(n) for storing tasks and the heap.

Solution

We first augment each task with its original index and sort the tasks based on their enqueue times. We then use a min-heap to keep track of tasks that are available. At each step, we:

Add all tasks available at the current time to the heap.
If the heap is not empty, pop the task with the smallest processing time (using the original index as a tie breaker) and update the current time by its processing time.
If the heap is empty, advance the current time to the next task's enqueue time. This process ensures that the CPU always processes the appropriate task and the order is maintained correctly.

Code Solutions

import heapq

class Solution:
    def getOrder(self, tasks):
        # Augment each task with its original index: (enqueueTime, processingTime, index)
        indexed_tasks = [(task[0], task[1], i) for i, task in enumerate(tasks)]
        # Sort tasks by enqueueTime
        indexed_tasks.sort(key=lambda x: x[0])
        
        result = []  # This list will store the order of task indices
        min_heap = []  # Heap to select the next task by processing time and index
        time = 0  # Current time
        i = 0  # Pointer to tasks in indexed_tasks list
        n = len(tasks)
        
        while i < n or min_heap:
            # If no available tasks, jump time to the next task's enqueueTime
            if not min_heap and time < indexed_tasks[i][0]:
                time = indexed_tasks[i][0]
            # Add all tasks that have become available by current time to the heap
            while i < n and indexed_tasks[i][0] <= time:
                enqueue_time, processing_time, index = indexed_tasks[i]
                heapq.heappush(min_heap, (processing_time, index))
                i += 1
            # Process the task at the top of the heap (shortest processing time then smallest index)
            proc_time, index = heapq.heappop(min_heap)
            time += proc_time  # Update the current time by the processing time of the task
            result.append(index)
        return result

# Example usage:
# sol = Solution()
# print(sol.getOrder([[1,2],[2,4],[3,2],[4,1]]))