MediumArrayGreedySortingUpdated Sep 2026

2895. Minimum Processing Time

Asked at JPMorgan

Difficulty

Medium

Time

O(n log n + m log m)

Space

O(1) extra

Pattern

Array

Companies

1

Problem

You have n processors. Each processor has 4 cores, and every core runs exactly one task. So the number of tasks is always 4 * n.

Each processor becomes free at a given time. You get processorTime, where processorTime[i] is the moment processor i is ready to start. You also get tasks, where tasks[j] is how long task j takes to run. A processor can only start after it is available, and it runs its four tasks on its four cores at the same time.

A processor finishes when its slowest task is done, so its finish time is availableTime + longestTask. Return the smallest possible time by which all tasks are finished, choosing which tasks go to which processor.

Two processors, four cores each

processorTime81001Processor 0 is ready at time 8, processor 1 at time 10.tasks2231874501234567Eight tasks must be split into two groups of four.
Each processor runs four tasks at once, so only its longest task decides when it finishes.

Constraints

  • ●1 <= n == processorTime.length <= 25000
  • ●1 <= tasks.length <= 10^5
  • ●0 <= processorTime[i] <= 10^9
  • ●1 <= tasks[i] <= 10^9
  • ●tasks.length == 4 * n

Examples

Example 1
InputprocessorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
Output16
WhyGive the four longest tasks (8,7,5,4) to the processor ready at time 8. It finishes at 8 + 8 = 16. The processor ready at 10 takes the rest (3,2,2,1) and finishes at 10 + 3 = 13. The overall finish time is the larger of the two, 16.
Example 2
InputprocessorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
Output23
WhyThe processor ready at 10 takes the long tasks 8,5,4,3 and finishes at 10 + 8 = 18. The processor ready at 20 takes 3,2,2,1 and finishes at 20 + 3 = 23. The answer is the maximum, 23.

Asked At

1 companies
CompanyDifficulty
JPMorganMediumView all JPMorgan questions →

How to Think About It

1

A processor finishes at availableTime + (longest task it runs). Only the longest of its four tasks matters.

2

Key insight: pair early processors with long tasks. Sort processors ascending and tasks descending, then give processor i the tasks at positions 4i..4i+3.

3

The finish time of processor i is processorTime[i] + tasks[4i] (its longest task). The answer is the maximum over processors.

4

Exchange argument: if an early processor had a shorter longest-task than a later one, swapping those tasks never increases the maximum.

5

Walkthrough: processors [8,10], tasks [2,2,3,1,8,7,4,5]. Tasks sorted desc [8,7,5,4,3,2,2,1]. Processor 8 takes 8,7,5,4 -> 16; processor 10 takes 3,2,2,1 -> 13. Answer 16.

Optimal Approach

Step 1: Sort processorTime ascending and tasks descending.
Step 2: res = max(processorTime[i] + tasks[4 * i] for i).
Step 3: Return res.

Time: O(n log n). Space: O(1) extra.

Sort processors up, tasks down, then group by four

tasks sorted descprocessor 8processor 108754322101234567Group 0 goes to the processor ready at 8, group 1 to the one readyat 10.longest task per processor8301Only the first task of each group matters: 8 and 3.finish = processorTime[i] + tasks[4*i]8 + 8 = 16, 10 + 3 = 13answer = max(16, 13) = 16
The earliest processor gets the four longest tasks, so its longest task is the biggest one overall.
ComplexityTime O(n log n + m log m)Space O(1) extraThe cost comes from sorting the processors and the tasks; the final scan is linear.

What Trips People Up in Real Interviews

1

Giving the longest tasks to the latest processor — exactly backwards.

2

Summing task durations per processor. Cores run in parallel, so only the longest task on each processor counts.

3

Sorting both arrays in the same direction.

4

Not explaining the exchange argument.

Solution Code

O(n log n + m log m) time
def minProcessingTime(processorTime, tasks):
    processorTime.sort()
    tasks.sort(reverse=True)
    return max(p + tasks[4 * i] for i, p in enumerate(processorTime))

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Processing Time problem?

Minimum Processing Time gives you processors (each with 4 cores and an availability time) and exactly `4n` tasks. Each core runs one task. Minimize the time when all tasks finish. The greedy: the earliest-available processor should take the longest tasks.

How do you solve Minimum Processing Time?

The optimal approach runs in O(n log n + m log m) time and O(1) extra space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Processing Time?

Minimum Processing Time is asked at JPMorgan. It is a medium difficulty problem.

What are common mistakes on Minimum Processing Time?
  • Giving the longest tasks to the latest processor — exactly backwards.
  • Summing task durations per processor. Cores run in parallel, so only the longest task on each processor counts.
  • Sorting both arrays in the same direction.
  • Not explaining the exchange argument.