Solution Explanation: Single-Threaded CPU

This problem requires scheduling tasks on a single-threaded CPU based on specific rules: prioritize shorter processing times, and if ties exist, use the smaller task index. The solution employs a combination of sorting and a priority queue (min-heap) for efficient task management.

Approach:

1. Data Augmentation: Each task [enqueueTime, processingTime] is augmented with its original index. This is crucial for breaking ties between tasks with equal processing times. The augmented task representation becomes [enqueueTime, processingTime, index].

2. Sorting: The tasks are sorted by enqueueTime in ascending order. This ensures that we process tasks in the order they become available.

3. Priority Queue (Min-Heap): A priority queue is used to store available tasks. The priority is determined by processingTime, and if ties exist, by the task's index. This guarantees that the CPU always selects the task with the shortest processing time and the smallest index in case of ties.

4. Simulation: The algorithm simulates the CPU's execution. A currentTime variable tracks the current time. The main loop continues as long as there are tasks in the priority queue or available tasks to add to it.

   • Idle CPU: If the priority queue is empty, the currentTime is updated to the earliest available task's enqueueTime or remains at the current value if no further tasks exist.

   • Add Available Tasks: All tasks whose enqueueTime is less than or equal to the currentTime are added to the priority queue.

   • Process Task: The task with the shortest processingTime (and smallest index in case of ties) is dequeued from the priority queue. Its index is appended to the result list, and currentTime is updated by adding the task's processingTime.

5. Result: The ans list, which accumulates task indices in the order of execution, is returned.

Time Complexity Analysis:

• Sorting the tasks: O(n log n)
• Adding and removing tasks from the priority queue: O(n log n) in the worst case. Each task is added and removed once. The heap operations (insertion and deletion) take O(log n) time.
• Iterating through the tasks: O(n)

Therefore, the overall time complexity is dominated by the sorting and priority queue operations, resulting in O(n log n).

Space Complexity Analysis:

• The priority queue stores at most n tasks at a time.
• The space used for the sorted tasks and the result list is O(n).

Thus, the overall space complexity is O(n).

Code Examples (Python):

import heapq
 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        for i in range(n):
            tasks[i].append(i) # add original index
 
        tasks.sort() # Sort by enqueueTime
 
        ans = []
        pq = []  # Min-heap (processingTime, index)
        curr_time = 0
        task_index = 0
 
        while task_index < n or pq:
            if not pq:
                curr_time = max(curr_time, tasks[task_index][0])
 
            while task_index < n and tasks[task_index][0] <= curr_time:
                heapq.heappush(pq, (tasks[task_index][1], tasks[task_index][2]))
                task_index += 1
 
            proc_time, task_idx = heapq.heappop(pq)
            ans.append(task_idx)
            curr_time += proc_time
 
        return ans

The code in other languages (Java, C++, Go) follows the same logic with appropriate data structures and syntax adjustments. The core algorithm remains consistent across all languages.