We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Single-Threaded CPU

Difficulty: Medium

Problem Description

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei to finish processing. You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

  • 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 will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
  • Once a task is started, the CPU will process the entire task without stopping.
  • The CPU can finish a task then start a new one instantly. Return the order in which the CPU will process the tasks.

Key Insights

  • The CPU processes tasks based on their availability and processing times.
  • When multiple tasks are available, the task with the shortest processing time is prioritized.
  • Tasks should be processed in the order they become available and based on their processing duration.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting and priority queue operations. Space Complexity: O(n) - for the priority queue and storing results.

Solution

To solve this problem, we will use a priority queue (min-heap) to efficiently select the next task to process based on the shortest processing time. The algorithm proceeds as follows:

  1. Sort the tasks based on their enqueue times.
  2. Use a priority queue to manage tasks that are currently available to process.
  3. Iterate through time, checking for newly available tasks and processing the current task based on the shortest processing time.
  4. Continue processing until all tasks are completed.

Code Solutions

import heapq

def getOrder(tasks):
    # Enrich tasks with their original index
    enriched_tasks = [(enqueue_time, processing_time, i) for i, (enqueue_time, processing_time) in enumerate(tasks)]
    # Sort tasks by enqueue time
    enriched_tasks.sort()
    
    result = []
    min_heap = []
    current_time = 0
    index = 0
    n = len(tasks)

    while index < n or min_heap:
        # Push all tasks that have become available by current_time
        while index < n and enriched_tasks[index][0] <= current_time:
            heapq.heappush(min_heap, (enriched_tasks[index][1], enriched_tasks[index][2]))  # (processing_time, index)
            index += 1
        
        if min_heap:
            # Pop the task with the shortest processing time
            processing_time, original_index = heapq.heappop(min_heap)
            result.append(original_index)
            current_time += processing_time  # Move time forward
        else:
            # If no tasks are available, move time to the next task's enqueue time
            current_time = enriched_tasks[index][0]

    return result
← Back to All Questions