Minimum Processing Time
MedPrompt
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 * n
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward but incorrect approach is to sort both the processor available times and the task durations and then pair them in the same order. This means the earliest available processor is assigned the four shortest tasks, the second earliest processor gets the next four shortest tasks, and so on.
Algorithm
- Sort the
processorTimearray in ascending order. - Sort the
tasksarray in ascending order. - Initialize a variable
maxCompletionTimeto 0. - Iterate through the processors from
i = 0ton-1. - For the
i-th processor, assign it thei-th group of 4 tasks from the sortedtasksarray (i.e., tasks at indices4*ito4*i+3). - The completion time for this processor is
processorTime[i] + tasks[4*i + 3](the longest task in its group). - Update
maxCompletionTime = max(maxCompletionTime, currentCompletionTime). - After the loop, return
maxCompletionTime.
Walkthrough
This method is based on a simple greedy idea: give the 'easiest' work (shortest tasks) to the 'best' processors (earliest available). However, this intuition is flawed because it can lead to a situation where a late-starting processor is paired with very long tasks, creating a bottleneck and a high overall completion time.
Let's see why this fails with an example: processorTime = [8, 10], tasks (sorted) = [1, 2, 2, 3, 4, 5, 7, 8].
- Processor at time 8 gets tasks
{1, 2, 2, 3}. Completion time:8 + 3 = 11. - Processor at time 10 gets tasks
{4, 5, 7, 8}. Completion time:10 + 8 = 18. - The result is
max(11, 18) = 18. The optimal answer is 16. This approach creates a bottleneck with the second processor.
import java.util.List;import java.util.Collections; class Solution { public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) { int n = processorTime.size(); Collections.sort(processorTime); Collections.sort(tasks); int maxCompletionTime = 0; for (int i = 0; i < n; i++) { // The longest task in the i-th group of 4 shortest tasks int currentMaxTask = tasks.get(4 * i + 3); int currentCompletionTime = processorTime.get(i) + currentMaxTask; if (currentCompletionTime > maxCompletionTime) { maxCompletionTime = currentCompletionTime; } } return maxCompletionTime; }}Complexity
Time
O(M log M + N log N), where N is the number of processors and M is the number of tasks. Since M = 4N, this simplifies to O(M log M) as sorting the tasks dominates the complexity.
Space
O(M), where M is the number of tasks. This is due to the space requirements of the sorting algorithm (Timsort) used by `Collections.sort` in Java.
Trade-offs
Pros
Simple to conceive and implement.
Uses a common sorting pattern.
Cons
Produces a non-optimal, incorrect result.
The greedy choice is based on a flawed intuition.
Solutions
Solution
class Solution {public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) { processorTime.sort((a, b)->a - b); tasks.sort((a, b)->a - b); int ans = 0, i = tasks.size() - 1; for (int t : processorTime) { ans = Math.max(ans, t + tasks.get(i)); i -= 4; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.