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.
The key to minimizing the maximum completion time is to use a counter-intuitive greedy strategy. To balance the workload, the processors that become available earliest should be assigned the tasks that take the longest to complete. This pairing prevents any single processor from becoming a significant bottleneck. The late-starting processors are given the shortest tasks, as their start time already contributes heavily to their total completion time.
Algorithm
- Sort the
processorTimearray in ascending order. - Sort the
tasksarray in descending order. - Initialize a variable
maxCompletionTimeto 0. - Iterate through the processors from
i = 0ton-1. - For the
i-th processor (processorTime[i]), assign it thei-th group of four tasks from the descending sortedtaskslist (i.e., tasks at indices4*ito4*i+3). - The longest task in this group is
tasks[4*i]. - The completion time for this processor is
processorTime[i] + tasks[4*i]. - Update
maxCompletionTime = max(maxCompletionTime, currentCompletionTime). - Return
maxCompletionTime.
Walkthrough
The problem is to minimize max(processorTime[i] + max_task_for_processor_i). This is a classic scheduling problem where to minimize the maximum of sums, you should pair the smallest elements of one set with the largest elements of another.
Let's trace this with the example: processorTime = [8, 10], tasks = [2,2,3,1,8,7,4,5].
- Sorted
processorTime(ascending):[8, 10]. - Sorted
tasks(descending):[8, 7, 5, 4, 3, 2, 2, 1]. - Processor at time 8 gets tasks
{8, 7, 5, 4}. Longest task is 8. Completion time:8 + 8 = 16. - Processor at time 10 gets tasks
{3, 2, 2, 1}. Longest task is 3. Completion time:10 + 3 = 13. - The result is
max(16, 13) = 16, which is the optimal solution.
import java.util.List;import java.util.Collections; class Solution { public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) { int n = processorTime.size(); // Sort processors by available time (ascending) Collections.sort(processorTime); // Sort tasks by duration (descending) Collections.sort(tasks, Collections.reverseOrder()); int maxCompletionTime = 0; // Pair earliest processors with longest tasks for (int i = 0; i < n; i++) { // The i-th processor gets the i-th group of 4 tasks. // The longest task in this group is at index 4*i. int currentMaxTask = tasks.get(4 * i); int currentCompletionTime = processorTime.get(i) + currentMaxTask; if (currentCompletionTime > maxCompletionTime) { maxCompletionTime = currentCompletionTime; } } return maxCompletionTime; }}An alternative implementation could sort tasks in ascending order and then iterate through them from the end to achieve the same pairing.
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 is the most time-consuming step.
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
Correctly finds the minimum possible completion time.
Efficient, with complexity dominated by sorting.
Cons
The greedy choice might not be immediately obvious without understanding the underlying principle.
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; }}class Solution: def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int: processorTime . sort() tasks . sort() ans = 0 i = len(tasks) - 1 for t in processorTime: ans = max(ans, t + tasks[i]) i -= 4 return ansclass Solution {public: int minProcessingTime(vector<int> &processorTime, vector<int> &tasks) { sort(processorTime.begin(), processorTime.end()); sort(tasks.begin(), tasks.end()); int ans = 0, i = tasks.size() - 1; for (int t : processorTime) { ans = max(ans, t + tasks[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.