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

Minimum Processing Time

Difficulty: Medium

Problem Description

You have a certain number of processors, each having 4 cores. The number of tasks to be executed is four times the number of processors. Each task must be assigned to a unique core, and each core can only be used once. You are given an array processorTime representing the time each processor becomes available and an array tasks representing how long each task takes to complete. Return the minimum time needed to complete all tasks.

Key Insights

  • Each processor can handle 4 tasks simultaneously due to its 4 cores.
  • The goal is to minimize the maximum completion time across all processors.
  • Sorting the tasks can help in efficiently assigning them to processors.
  • Greedy algorithms can be used to optimally assign the longest tasks to the soonest available processors.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Sort the Tasks: Start by sorting the tasks in descending order to prioritize assigning longer tasks first.
  2. Initialize a Min-Heap: Use a min-heap to keep track of when each processor will be free. The min-heap allows us to efficiently get the processor that will be available the soonest.
  3. Assign Tasks: For each task, pop the processor with the earliest available time from the heap, assign the task to it, and push it back into the heap with the updated finish time (available time + task duration).
  4. Calculate Completion Time: The final result will be the maximum of the completion times from all processors.

Code Solutions

import heapq

def minimumProcessingTime(processorTime, tasks):
    # Sort tasks in descending order
    tasks.sort(reverse=True)
    
    # Min-heap to track the completion time of each processor
    heap = []
    
    # Initialize the heap with the initial available times of the processors
    for time in processorTime:
        heapq.heappush(heap, time)
    
    # Assign tasks to processors
    for task in tasks:
        # Get the earliest available processor
        earliest_available = heapq.heappop(heap)
        # Update the completion time for this processor
        finish_time = earliest_available + task
        # Push the updated time back to the heap
        heapq.heappush(heap, finish_time)
    
    # The answer is the maximum finish time among all processors
    return max(heap)
← Back to All Questions