Minimum Processing Time
Asked at JPMorgan
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| JPMorgan | Medium | View all JPMorgan questions → |
How to Think About It
A processor finishes at availableTime + (longest task it runs). Only the longest of its four tasks matters.
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.
The finish time of processor i is processorTime[i] + tasks[4i] (its longest task). The answer is the maximum over processors.
Exchange argument: if an early processor had a shorter longest-task than a later one, swapping those tasks never increases the maximum.
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.
What Trips People Up in Real Interviews
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.
Solution Code
def minProcessingTime(processorTime, tasks):
processorTime.sort()
tasks.sort(reverse=True)
return max(p + tasks[4 * i] for i, p in enumerate(processorTime))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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.