Skip to main content
Talentd

Minimum Processing Time - Solution & Explanation

MediumArrayGreedySorting16 min readAsked at: Adobe, Google, Jpmorgan +1
Practice this problem

Problem Statement

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 <= 25000
  • 1 <= tasks.length <= 105
  • 0 <= processorTime[i] <= 109
  • 1 <= tasks[i] <= 109
  • tasks.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.

The C solution involves sorting the tasks and processorTime arrays. We process tasks in groups of four assigned to each processor. The largest possible processing end time is computed for each group, which helps determine the minimal time to complete all tasks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m log m + n log n) where m = 4n is the number of tasks and n is the number of processors.
Space Complexity: O(1) as we use constant extra space.

Try this approach in the editor →

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.

This C solution uses the two-pointer technique after sorting the processorTime and tasks arrays. It aims to complete tasks from the processing cores with a greedy approach.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m log m + n log n) because of the sorting.
Space Complexity: O(1).

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting with Task Distribution Optimization

Time Complexity: O(m log m + n log n) where m = 4n is the number of tasks and n is the number of processors.
Space Complexity: O(1) as we use constant extra space.

Greedy Assignment with Two-Pointer Technique

Time Complexity: O(m log m + n log n) because of the sorting.
Space Complexity: O(1).

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting with Task Distribution OptimizationO(n log n)O(1)Best general solution when tasks must be grouped per processor
Greedy Assignment with Two-Pointer TechniqueO(n log n)O(1)Useful when implementing explicit task grouping after sorting

Video Solution

2895. Minimum Processing Time 🔥 || Greedy + Sorting 🔥 || (C++,JAVA,Python)🔥 • Ayush Rao • 1,354 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Processing Time with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays