Minimum Processing Time

Minimum Processing Time

What is this problem about?

The Minimum Processing Time problem gives you a list of processor speeds and a list of tasks, each with a processing time. Each processor can handle exactly a fixed number of tasks (say 4), and all tasks assigned to a processor finish at the same time (determined by the slowest task on that processor plus the processor speed). Your goal is to assign tasks to processors to minimize the total time for all tasks to finish. This is a classic Minimum Processing Time interview question involving greedy scheduling.

Why is this asked in interviews?

Companies like Akuna Capital, Adobe, and Nutanix ask this to evaluate greedy reasoning and sorting skills. Real-world scheduling and task allocation problems underpin systems design in distributed computing. The array, sorting, and greedy interview pattern is central, and interviewers want to see whether candidates can identify the optimal pairing strategy without exhaustive enumeration.

Algorithmic pattern used

The optimal strategy uses sorting and greedy pairing. Sort processors in descending order (slowest first) and tasks in descending order (longest first). Assign the top-k tasks (by time) to the slowest processor, the next k tasks to the next slowest, and so on. The finish time for each group is processorSpeed + max(task times in group). Since tasks are sorted, the max in each group is always the first task assigned to it. Answer = maximum finish time across all processors.

Example explanation

Processors: [3, 1] (each handles 2 tasks). Tasks: [5, 4, 2, 1].

• Sort processors descending: [3, 1].
• Sort tasks descending: [5, 4, 2, 1].
• Assign [5,4] to processor 3: finish time = 3 + 5 = 8.
• Assign [2,1] to processor 1: finish time = 1 + 2 = 3.
• Answer = max(8, 3) = 8.

Common mistakes candidates make

• Pairing the slowest processor with the shortest tasks (which actually maximizes time).
• Sorting in the wrong direction for either processors or tasks.
• Not taking the maximum across all processors as the final answer.
• Misunderstanding that all tasks on a processor finish simultaneously at the max time.

Interview preparation tip

Greedy assignment problems often rely on the "match extremes" insight: pair your heaviest burden with your strongest resource. For Minimum Processing Time, always ask: which processor can afford the longest tasks without becoming the bottleneck? Sorting both lists and matching them in order is almost always the key step. Practice similar greedy scheduling problems — they form a surprisingly large portion of interview questions at mid-level companies.