Minimum Processing Time - Video Solutions

Problem Overview: You are given two arrays: processorTime and tasks. Each processor must handle exactly four tasks. A processor can only start processing after its own setup time, and the total completion time for that processor depends on the largest task assigned to it. The goal is to distribute tasks so the overall finishing time across all processors is minimized.

Approach 1: Sorting with Task Distribution Optimization (O(n log n) time, O(1) extra space)

The key observation is that each processor receives exactly four tasks, and the processor’s finish time is dominated by the largest task assigned to it. To minimize the maximum completion time, assign larger tasks to processors with smaller setup times. Start by sorting processorTime in ascending order and tasks in descending order. Then distribute tasks in groups of four: processor i receives tasks starting from index 4 * i. Because the tasks array is sorted descending, the first element in each group represents the largest task for that processor. Compute processorTime[i] + tasks[4*i] and track the maximum across all processors. Sorting dominates the runtime, giving O(n log n) time with O(1) extra space if sorting in place. This approach relies heavily on sorting and a simple greedy assignment strategy.

Approach 2: Greedy Assignment with Two-Pointer Technique (O(n log n) time, O(1) space)

This version expresses the same greedy logic using two pointers after sorting. Sort processorTime in ascending order and tasks in descending order. Use one pointer i to iterate through processors and another pointer j to track the current largest unassigned task. For each processor, assign the next four tasks starting from j. Only the first task in that group determines the processor’s completion time because it is the largest among the four. Update the answer with processorTime[i] + tasks[j] and move j += 4. The two-pointer pattern makes the distribution explicit and keeps the implementation clean. Complexity remains O(n log n) due to sorting, with constant additional memory. The arrays themselves are the main data structures, making this a classic array greedy scheduling problem.

Recommended for interviews: The sorting-based greedy strategy is what interviewers expect. It demonstrates that you recognized the constraint of exactly four tasks per processor and reduced the problem to pairing smallest processor setup times with largest task groups. Brute-force simulation would be inefficient and unnecessary, while the greedy sorting approach shows strong algorithmic intuition and clean complexity analysis.