Minimum Processing Time solution and explanation
Google
7 more videos on this problem
2895. Minimum Processing Time 🔥 || Greedy + Sorting 🔥 || (C++,JAVA,Python)🔥Ayush Rao · 5:23 · 1K views
2894. Minimum Processing Time (Leetcode Medium)Programming Live with Larry · 9:05 · 852 views
100085 Minimum Processing Time || leetcode || contest365 || weekly contest || solution || java codeSsquare · 1:01 · 713 views
LeetCode 2895 Minimum Processing TimeThinkCode · 4:34 · 690 views
Minimum Processing Time | Leetcode 2895 | Greedy | Contest 366Tech Courses · 7:35 · 594 views
100085. Minimum Processing Time | leetcode | Weekly Contest 366.Optimization · 0:21 · 413 views
Leetcode 2895 Minimum Processing TimeLeetcoder · 2:44 · 166 views
Minimum Processing Time [Leetcode-2895] | C++DSA_decoded · 2:16 · 42 views
The problem
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
Approach overview
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.
Approach 1: Sorting with Task Distribution Optimization
In this approach, the key idea is to sort the task times and the processor availability times to efficiently allocate tasks such that the maximum processing time is minimized.
Sort the tasks in descending order and processors by their availability. Assign the largest unassigned tasks to the most available processors iteratively.
def min_time(processorTime, tasks):
processorTime.sort()
tasks.sort(reverse=True)
result = 0
num_processors = len(processorTime)
for i in range(num_processors):
max_time = 0
for j in range(4):
task_index = i * 4 + j
completion_time = processorTime[i] + tasks[task_index]
max_time = max(max_time, completion_time)
result = max(result, max_time)
return result
# Example usage
processorTime = [8, 10]
tasks = [2, 2, 3, 1, 8, 7, 4, 5]
print(min_time(processorTime, tasks))import java.util.Arrays;
public class Main {
public static int minTime(int[] processorTime, int[] tasks) {
Arrays.sort(processorTime);
// Sorting in descending order
Integer[] taskObjects = Arrays.stream(tasks).boxed().toArray(Integer[]::new);
Arrays.sort(taskObjects, (a, b) -> b - a);
int result = 0;
for (int i = 0; i < processorTime.length; i++) {
int maxTime = 0;
for (int j = 0; j < 4; j++) {
int taskTime = taskObjects[i * 4 + j];
int completionTime = processorTime[i] + taskTime;
maxTime = Math.max(maxTime, completionTime);
}
result = Math.max(result, maxTime);
}
return result;
}
public static void main(String[] args) {
int[] processorTime = {8, 10};
int[] tasks = {2, 2, 3, 1, 8, 7, 4, 5};
System.out.println(minTime(processorTime, tasks));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minTime(vector<int>& processorTime, vector<int>& tasks) {
sort(processorTime.begin(), processorTime.end());
sort(tasks.begin(), tasks.end(), greater<int>());
int result = 0, n = processorTime.size();
for (int i = 0; i < n; ++i) {
int maxTime = 0;
for (int j = 0; j < 4; ++j) {
int taskIndex = i * 4 + j;
maxTime = max(maxTime, processorTime[i] + tasks[taskIndex]);
}
result = max(result, maxTime);
}
return result;
}
int main() {
vector<int> processorTime = {8, 10};
vector<int> tasks = {2, 2, 3, 1, 8, 7, 4, 5};
cout << minTime(processorTime, tasks) << endl;
return 0;
}function minTime(processorTime, tasks) {
processorTime.sort((a, b) => a - b);
tasks.sort((a, b) => b - a);
let result = 0;
for (let i = 0; i < processorTime.length; i++) {
let maxTime = 0;
for (let j = 0; j < 4; j++) {
let completionTime = processorTime[i] + tasks[i * 4 + j];
maxTime = Math.max(maxTime, completionTime);
}
result = Math.max(result, maxTime);
}
return result;
}
console.log(minTime([8, 10], [2, 2, 3, 1, 8, 7, 4, 5]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
int min_time(int* processorTime, int processorSize, int* tasks, int taskSize) {
// Sort tasks in descending order
qsort(tasks, taskSize, sizeof(int), compare);
// Sort processors' availability times
qsort(processorTime, processorSize, sizeof(int), compare);
int result = 0;
for (int i = 0; i < processorSize; i++) {
int maxTime = 0;
for (int j = 0; j < 4; j++) {
int taskIndex = i * 4 + j;
int endTime = processorTime[i] + tasks[taskIndex];
if (endTime > maxTime) {
maxTime = endTime;
}
}
if (maxTime > result) {
result = maxTime;
}
}
return result;
}
int main() {
int processorTime[] = {8, 10};
int tasks[] = {2, 2, 3, 1, 8, 7, 4, 5};
int processorSize = 2;
int taskSize = 8;
printf("%d\n", min_time(processorTime, processorSize, tasks, taskSize));
return 0;
}using System;
public class Solution {
public static int MinTime(int[] processorTime, int[] tasks) {
Array.Sort(processorTime);
Array.Sort(tasks, (a, b) => b.CompareTo(a)); // Sort tasks descending
int result = 0;
for (int i = 0; i < processorTime.Length; i++) {
int maxTime = 0;
for (int j = 0; j < 4; j++) {
int taskTime = tasks[i * 4 + j];
maxTime = Math.Max(maxTime, processorTime[i] + taskTime);
}
result = Math.Max(result, maxTime);
}
return result;
}
public static void Main() {
int[] processorTime = {8, 10};
int[] tasks = {2, 2, 3, 1, 8, 7, 4, 5};
Console.WriteLine(MinTime(processorTime, tasks));
}
}The Python solution succinctly implements sorting and task distribution in a single function. It follows the same logic of sorting and grouping tasks to balance the workload efficiently among processors.
Time Complexity: O(m log m + n log n), where m = 4n tasks are sorted, and n processors.
Space Complexity: O(1) as there are no additional data allocations.
Approach 2: Greedy Assignment with Two-Pointer Technique
This approach uses a two-pointer technique. With one pointer on the processors' array and one on the task array, use a greedy approach to find the minimum completion time by balancing tasks based on processor availability without explicit sorting.
def min_time(processorTime, tasks):
processorTime.sort()
tasks.sort()
result = 0
task_index = len(tasks) - 1
for i in range(len(processorTime)):
for _ in range(4):
result = max(result, processorTime[i] + tasks[task_index])
task_index -= 1
return result
processorTime = [8, 10]
tasks = [2, 2, 3, 1, 8, 7, 4, 5]
print(min_time(processorTime, tasks))import java.util.Arrays;
public class Main {
public static int minTime(int[] processorTime, int[] tasks) {
Arrays.sort(processorTime);
Arrays.sort(tasks);
int result = 0;
int taskIndex = tasks.length - 1;
for (int i = 0; i < processorTime.length; i++) {
for (int j = 0; j < 4; j++) {
result = Math.max(result, processorTime[i] + tasks[taskIndex--]);
}
}
return result;
}
public static void main(String[] args) {
int[] processorTime = {8, 10};
int[] tasks = {2, 2, 3, 1, 8, 7, 4, 5};
System.out.println(minTime(processorTime, tasks));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minTime(vector<int>& processorTime, vector<int>& tasks) {
sort(processorTime.begin(), processorTime.end());
sort(tasks.begin(), tasks.end());
int result = 0;
int taskIndex = tasks.size() - 1;
for (int i = 0; i < processorTime.size(); i++) {
for (int j = 0; j < 4; j++) {
result = max(result, processorTime[i] + tasks[taskIndex--]);
}
}
return result;
}
int main() {
vector<int> processorTime = {8, 10};
vector<int> tasks = {2, 2, 3, 1, 8, 7, 4, 5};
cout << minTime(processorTime, tasks) << endl;
return 0;
}function minTime(processorTime, tasks) {
processorTime.sort((a, b) => a - b);
tasks.sort((a, b) => a - b);
let result = 0;
let taskIndex = tasks.length - 1;
for (let i = 0; i < processorTime.length; i++) {
for (let j = 0; j < 4; j++) {
result = Math.max(result, processorTime[i] + tasks[taskIndex--]);
}
}
return result;
}
console.log(minTime([8, 10], [2, 2, 3, 1, 8, 7, 4, 5]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int min_time(int* processorTime, int processorSize, int* tasks, int taskSize) {
qsort(processorTime, processorSize, sizeof(int), compare);
qsort(tasks, taskSize, sizeof(int), compare);
int taskIndex = taskSize - 1;
int result = 0;
for (int i = 0; i < processorSize; i++) {
int maxTime = processorTime[i];
for (int j = 0; j < 4; j++) {
maxTime = processorTime[i] + tasks[taskIndex--];
if (maxTime > result) result = maxTime;
}
}
return result;
}
int main() {
int processorTime[] = {8, 10};
int tasks[] = {2, 2, 3, 1, 8, 7, 4, 5};
int processorSize = 2;
int taskSize = 8;
printf("%d\n", min_time(processorTime, processorSize, tasks, taskSize));
return 0;
}using System;
public class Solution {
public static int MinTime(int[] processorTime, int[] tasks) {
Array.Sort(processorTime);
Array.Sort(tasks);
int result = 0;
int taskIndex = tasks.Length - 1;
foreach (var pTime in processorTime) {
for (int j = 0; j < 4; j++) {
result = Math.Max(result, pTime + tasks[taskIndex--]);
}
}
return result;
}
public static void Main() {
int[] processorTime = {8, 10};
int[] tasks = {2, 2, 3, 1, 8, 7, 4, 5};
Console.WriteLine(MinTime(processorTime, tasks));
}
}The Python variant streams through processors after sorting tasks in ascending order, applying the available tasks using two-pointers. It is efficient and aligns with our approach objective.
Time Complexity: O(m log m + n log n) due to sorting.
Space Complexity: O(1) as it uses iterative reduction.
Approach 3: Greedy + Sorting
To minimize the time required to process all tasks, the four tasks with the longest processing time should be assigned to the processors that become idle earliest.
Therefore, we sort the processors by their idle time and sort the tasks by their processing time. Then, we assign the four tasks with the longest processing time to the processor that becomes idle earliest, and calculate the maximum end time.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of tasks.
function minProcessingTime(processorTime: number[], tasks: number[]): number {
processorTime.sort((a, b) => a - b);
tasks.sort((a, b) => a - b);
let [ans, i] = [0, tasks.length - 1];
for (const t of processorTime) {
ans = Math.max(ans, t + tasks[i]);
i -= 4;
}
return ans;
}func minProcessingTime(processorTime []int, tasks []int) (ans int) {
sort.Ints(processorTime)
sort.Ints(tasks)
i := len(tasks) - 1
for _, t := range processorTime {
ans = max(ans, t+tasks[i])
i -= 4
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting with Task Distribution Optimization | Time Complexity: |
| Greedy Assignment with Two-Pointer Technique | Time Complexity: |
| Greedy + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Task Distribution Optimization | O(n log n) | O(1) | Best general solution when tasks must be grouped per processor |
| Greedy Assignment with Two-Pointer Technique | O(n log n) | O(1) | Useful when implementing explicit task grouping after sorting |
Frequently asked questions
Is Minimum Processing Time easy or hard?
Minimum Processing Time is considered a medium-level problem. The implementation is short, but recognizing the greedy insight—pairing fastest processors with largest task groups—requires understanding of sorting-based optimization.
Minimum Processing Time Python/Java solution
In Python or Java, the implementation sorts processorTime ascending and tasks descending, then iterates through processors assigning four tasks each. The result is computed using processorTime[i] + tasks[4*i]. Both languages achieve O(n log n) time and constant extra space.
How to solve Minimum Processing Time in O(n)?
A true O(n) solution is generally not feasible because sorting is required to optimally pair processors and tasks. The greedy strategy depends on ordering processors by setup time and tasks by duration. This sorting step leads to an O(n log n) overall complexity.
What is the best approach for Minimum Processing Time?
The optimal approach uses a greedy sorting strategy. Sort processor setup times in ascending order and task durations in descending order, then assign tasks in groups of four to each processor. The largest task in each group determines the processor’s completion time. This minimizes the global maximum finish time with O(n log n) complexity.
Is Minimum Processing Time asked at Google/Amazon/Meta?
Greedy scheduling and task assignment problems similar to Minimum Processing Time appear in interviews at companies like Amazon, Google, and Meta. Variations often test sorting-based greedy strategies, load balancing, and minimizing maximum completion time.
What data structure is used in Minimum Processing Time?
The solution primarily uses arrays combined with sorting. After sorting, tasks are assigned in groups using simple index arithmetic or a two-pointer approach. No advanced data structures like heaps or hash maps are required.
What is the time complexity of Minimum Processing Time?
The time complexity is O(n log n) because both the processorTime and tasks arrays are sorted. After sorting, assigning tasks to processors takes linear time O(n). The space complexity is O(1) if sorting is done in place.