Problem Description

You have a certain number of processors, and each processor has exactly 4 cores. The total number of tasks you need to execute is four times the number of processors (so if you have n processors, you have 4n tasks).

Each task must be assigned to a unique core, meaning once a core is used for a task, it cannot be used again. Since each processor has 4 cores and can only be used once, each processor will handle exactly 4 tasks.

You are given two arrays:

• processorTime: An array where processorTime[i] represents the time when processor i becomes available to start processing tasks
• tasks: An array where tasks[j] represents how long task j takes to complete

When a processor becomes available at time t and is assigned a task that takes duration d, the task will complete at time t + d. All 4 cores of a processor start working simultaneously when the processor becomes available.

Your goal is to assign all tasks to processors in a way that minimizes the total time needed to complete all tasks. The total completion time is determined by the last task to finish across all processors.

For example, if you have 2 processors becoming available at times [0, 10] and 8 tasks with durations [2, 3, 1, 4, 5, 6, 7, 8], you need to assign 4 tasks to each processor. The completion time for each processor would be its availability time plus the maximum duration among its assigned tasks.

Return the minimum possible time when all tasks are completed.

Intuition

Think about what determines when all tasks are completed - it's the processor that finishes last. For each processor, its completion time equals its start time plus the duration of its longest task (since all 4 cores work in parallel).

The key insight is that we want to minimize the maximum completion time across all processors. This is a classic min-max optimization problem.

Consider this: if we have a processor that becomes available early, we can afford to give it longer tasks because it has a "head start". Conversely, a processor that becomes available late should get shorter tasks to avoid extending the overall completion time.

This leads us to a greedy pairing strategy: match early processors with long tasks, and late processors with short tasks. More specifically:

• The earliest available processor should handle the 4 longest tasks
• The second earliest processor should handle the next 4 longest tasks
• And so on...

Why does this work? Consider any processor p with availability time t. Among the 4 tasks assigned to it, only the longest one matters for determining when this processor finishes (since all 4 cores work in parallel). So we're essentially pairing each processor with the longest task in its group of 4.

By sorting processors in ascending order of availability time and tasks in ascending order of duration, we can systematically assign tasks in groups of 4. Starting from the end of the sorted tasks array (longest tasks), we assign 4 tasks to each processor in order. This ensures that the earliest processors get the longest tasks, balancing out the completion times across all processors.

The final answer is the maximum of processorTime[i] + max_task_duration_for_processor_i across all processors.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows the greedy strategy we identified: pair early processors with long tasks.

Step 1: Sort both arrays

• Sort processorTime in ascending order to get processors from earliest to latest availability
• Sort tasks in ascending order to arrange tasks from shortest to longest duration

processorTime.sort()
tasks.sort()

Step 2: Assign tasks to processors We iterate through each processor and assign it the 4 longest remaining tasks. Since tasks are sorted in ascending order, the longest tasks are at the end of the array.

• Initialize ans = 0 to track the maximum completion time
• Start with index i = len(tasks) - 1 pointing to the longest task
• For each processor with availability time t:
  • The processor will handle tasks at indices [i, i-1, i-2, i-3]
  • Among these 4 tasks, the one at index i has the maximum duration
  • The completion time for this processor is t + tasks[i]
  • Update the overall maximum: ans = max(ans, t + tasks[i])
  • Move the index backward by 4: i -= 4

ans = 0
i = len(tasks) - 1
for t in processorTime:
    ans = max(ans, t + tasks[i])
    i -= 4

Why we only check tasks[i]: Since tasks is sorted, among the 4 tasks assigned to each processor (indices [i-3, i-2, i-1, i]), the task at index i has the maximum duration. All 4 cores work in parallel, so only the longest task determines when this processor finishes.

Time Complexity: O(n log n + m log m) where n is the number of processors and m is the number of tasks. The sorting operations dominate the complexity.

Space Complexity: O(1) if we can sort in-place, otherwise O(n + m) for the sorting space.

Example Walkthrough

Let's walk through a concrete example with 2 processors and 8 tasks.

Given:

• processorTime = [8, 10] (processors become available at times 8 and 10)
• tasks = [2, 2, 3, 1, 8, 7, 4, 5] (8 tasks with various durations)

Step 1: Sort both arrays

• After sorting processorTime: [8, 10] (already sorted)
• After sorting tasks: [1, 2, 2, 3, 4, 5, 7, 8]

Step 2: Assign tasks to processors

We start from the end of the sorted tasks array (longest tasks first) and assign 4 tasks to each processor:

First processor (available at time 8):

• Starting index i = 7 (last element)
• Assigns tasks at indices [4, 5, 6, 7] → tasks with durations [4, 5, 7, 8]
• All 4 cores work in parallel, so completion time = 8 + max(4, 5, 7, 8) = 8 + 8 = 16
• Update ans = max(0, 16) = 16
• Move index: i = 7 - 4 = 3

Second processor (available at time 10):

• Current index i = 3
• Assigns tasks at indices [0, 1, 2, 3] → tasks with durations [1, 2, 2, 3]
• All 4 cores work in parallel, so completion time = 10 + max(1, 2, 2, 3) = 10 + 3 = 13
• Update ans = max(16, 13) = 16

Result: The minimum time to complete all tasks is 16.

Why this is optimal:

• We gave the longest tasks [4, 5, 7, 8] to the processor that starts earlier (time 8)
• We gave the shorter tasks [1, 2, 2, 3] to the processor that starts later (time 10)
• This balances the completion times: 16 vs 13
• If we had done the opposite (short tasks to early processor, long tasks to late processor), we'd get completion times of 11 vs 18, with overall time of 18 (worse!)

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n log n + m log m) where n is the number of tasks and m is the number of processors. Since we have two sorting operations - processorTime.sort() takes O(m log m) time and tasks.sort() takes O(n log n) time. The for loop iterates through all processors (m iterations) with constant time operations inside, contributing O(m) time. Therefore, the overall time complexity is dominated by the sorting operations: O(n log n + m log m).

However, given that each processor handles exactly 4 tasks (as seen from i -= 4), we have the relationship n = 4m. Substituting this relationship: O(n log n + (n/4) log(n/4)) = O(n log n + n/4 * log n) = O(n log n).

The space complexity is O(log n) which comes from the sorting algorithm's recursive call stack. Python's built-in sort (Timsort) uses O(log n) space in the worst case for the recursion stack when sorting n elements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Task Assignment Direction

A common mistake is assigning the shortest tasks to the earliest processors instead of the longest tasks. This seems intuitive ("start with easy tasks") but actually leads to suboptimal results.

Wrong approach:

# Assigning shortest tasks to earliest processors
task_index = 0
for processor_start_time in processorTime:
    max_completion_time = max(max_completion_time, 
                             processor_start_time + tasks[task_index + 3])
    task_index += 4

Why it's wrong: This leaves the longest tasks for the latest processors, causing unnecessarily long completion times.

Solution: Always pair early processors with long tasks to maximize parallel processing efficiency.

2. Forgetting to Sort Arrays

Another pitfall is forgetting to sort one or both arrays before assignment, which breaks the greedy strategy entirely.

Wrong approach:

# Missing sort operations
max_completion_time = 0
task_index = len(tasks) - 1
for processor_start_time in processorTime:
    max_completion_time = max(max_completion_time, 
                             processor_start_time + tasks[task_index])
    task_index -= 4

Solution: Always sort both arrays first - processorTime in ascending order and tasks in ascending order before applying the assignment logic.

3. Checking Wrong Task Duration

When assigning 4 tasks to a processor, mistakenly checking a task other than the maximum duration task for that processor.

Wrong approach:

# Checking task at wrong index (not the maximum among the 4)
for processor_start_time in processorTime:
    max_completion_time = max(max_completion_time, 
                             processor_start_time + tasks[task_index - 3])
    task_index -= 4

Why it's wrong: Since all 4 cores work in parallel, the processor's completion time depends on its longest task, not any arbitrary task.

Solution: Always use tasks[task_index] (the largest among the 4 assigned tasks) when calculating completion time.

4. Index Out of Bounds

Not handling edge cases or assuming array sizes without validation.

Improved defensive code:

def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
    # Validate input
    if not processorTime or not tasks:
        return 0
    if len(tasks) != 4 * len(processorTime):
        raise ValueError("Tasks count must be 4 times processor count")
  
    processorTime.sort()
    tasks.sort()
  
    max_completion_time = 0
    task_index = len(tasks) - 1
  
    for processor_start_time in processorTime:
        if task_index < 0:  # Safety check
            break
        max_completion_time = max(max_completion_time, 
                                 processor_start_time + tasks[task_index])
        task_index -= 4
  
    return max_completion_time