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.
Example 1:
Input: processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
Output: 16
Explanation:
Assign the tasks at indices 4, 5, 6, 7 to the first processor which becomes available at time = 8, and the tasks at indices 0, 1, 2, 3 to the second processor which becomes available at time = 10.
The time taken by the first processor to finish the execution of all tasks is max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16.
The time taken by the second processor to finish the execution of all tasks is max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13.
Example 2:
Input: processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
Output: 23
Explanation:
Assign the tasks at indices 1, 4, 5, 6 to the first processor and the others to the second processor.
The time taken by the first processor to finish the execution of all tasks is max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18.
The time taken by the second processor to finish the execution of all tasks is max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23.
Constraints:
1 <= n == processorTime.length <= 250001 <= tasks.length <= 1050 <= processorTime[i] <= 1091 <= tasks[i] <= 109tasks.length == 4 * nTo solve #2895 Minimum Processing Time, observe that each processor can handle exactly 4 tasks and the total completion time for a processor depends on its base processing time plus the maximum task time assigned to it. This makes the assignment strategy crucial.
A common greedy approach is to sort the processor times in ascending order and the task durations in descending order. By pairing the fastest processors with the largest remaining tasks, you minimize the maximum finishing time across all processors. After sorting, group tasks in batches of four and assign each batch to the next available processor.
During assignment, track the maximum completion time as processorTime[i] + largestTaskInGroup. The overall answer is the maximum of these values. Sorting dominates the runtime, making the approach efficient for large inputs.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) or O(n) depending on sorting implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
It’s optimal to make the processor with earlier process time run 4 longer tasks.****
The largest <code>processTime[i] + tasks[j]</code> (when matched) is the answer.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Minimum Processing Time are common in coding interviews because they test greedy thinking, sorting strategies, and reasoning about minimizing maximum completion time. Variants of task scheduling frequently appear in technical interviews.
The optimal approach uses a greedy strategy combined with sorting. Sort processor times in ascending order and task durations in descending order, then assign tasks in groups of four to processors. This minimizes the maximum completion time across all processors.
Basic arrays and sorting utilities are sufficient for this problem. No advanced data structures are required, as the greedy logic works by sorting and iterating through the arrays efficiently.
Sorting tasks in descending order ensures that the largest tasks are assigned first to the fastest processors. Since each processor's completion time depends on the largest task it receives, this pairing helps minimize the overall processing time.