LeetCode 2895 - Minimum Processing Time

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem gives us two arrays:

processorTime, where each value represents the time when a processor becomes available
tasks, where each value represents how long a task takes to execute

Each processor has exactly 4 cores, and each core can execute exactly one task. Since there are n processors and each processor has 4 cores, the total number of tasks is always 4 * n.

A processor can start executing tasks only after its availability time. Once available, all four of its cores can work in parallel. Because the four tasks assigned to a processor run simultaneously, the completion time for that processor is determined by the slowest task assigned to it.

If a processor becomes available at time p and receives tasks with durations [a, b, c, d], then its finishing time is:

p + max(a, b, c, d)

The overall system completion time is the maximum finishing time among all processors. Our goal is to assign tasks to processors in a way that minimizes this overall completion time.

The constraints are important:

processorTime.length <= 25000
tasks.length <= 100000

This immediately tells us that exponential or factorial assignment strategies are impossible. Since the number of tasks can reach one hundred thousand, we should expect an efficient algorithm, likely involving sorting and greedy assignment.

The problem also guarantees:

Every processor gets exactly 4 tasks
Every task is assigned exactly once
tasks.length == 4 * n

This removes the need to handle uneven distribution.

Several edge cases are worth thinking about upfront:

All processors may become available at the same time
Task durations may vary dramatically
Some processors may be much slower to become available than others
The largest task durations dominate the final answer because processor completion depends only on the maximum assigned task

A naive implementation might distribute tasks arbitrarily or greedily in the wrong direction, which can produce suboptimal results.

Approaches

Brute Force Approach

The brute force idea is to try every possible assignment of tasks to processors.

Since each processor must receive exactly 4 tasks, we could:

Generate all possible ways to partition the tasks into groups of 4
Assign those groups to processors
Compute the maximum completion time for each assignment
Return the minimum result

This works because it explicitly checks every valid arrangement, so the optimal answer will eventually be found.

However, the number of possible assignments grows explosively. Even for relatively small inputs, the number of ways to partition and assign tasks becomes astronomically large. With up to 100000 tasks, brute force is completely infeasible.

We need a smarter observation.

Key Insight

The important observation is that for each processor, only the largest task assigned to it matters.

If a processor gets tasks [1, 2, 3, 100], the completion time is determined entirely by 100.

This means the optimization problem becomes:

How do we distribute the largest tasks?

Suppose we sort:

processorTime in ascending order
tasks in descending order

Then we assign tasks in groups of 4:

The earliest available processor gets the largest remaining 4 tasks
The next processor gets the next 4 largest tasks
And so on

Why does this work?

The processors with smaller availability times are more capable of absorbing large tasks without increasing the global maximum too much. Meanwhile, processors that start later should receive smaller tasks.

This is a classic greedy matching strategy:

Small processor times pair with large task times
Large processor times pair with small task times

Since each processor's finishing time depends only on its largest assigned task, after sorting tasks descending, the first task in each group of 4 determines the processor's contribution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible task assignments
Optimal Greedy + Sorting	O(n log n + m log m)	O(1) or O(log n) depending on sort	Sort processors and tasks, then greedily pair them

Here, m = tasks.length and n = processorTime.length.

Algorithm Walkthrough

Sort processorTime in ascending order.

This ensures processors that become available earlier are handled first. These processors are best suited to take larger tasks because they start sooner. 2. Sort tasks in descending order.

The largest tasks are the most dangerous because they dominate processor completion time. We want to distribute them carefully. 3. Assign tasks in groups of 4.

Since every processor has exactly 4 cores, every processor receives exactly 4 tasks. 4. For processor i, the relevant largest task is tasks[i * 4].

Because tasks are sorted descending, the first task in each group of 4 is the largest one assigned to that processor. 5. Compute the completion time for processor i:

processorTime[i] + tasks[i * 4]

The other three tasks assigned to that processor are smaller or equal, so they do not affect the completion time. 6. Track the maximum completion time across all processors.

This maximum represents the total time needed to finish all tasks. 7. Return the maximum value found.

Why it works

The greedy strategy works because the only important task for a processor is its largest assigned task. By sorting processors ascending and tasks descending, we pair earlier processors with larger tasks and later processors with smaller tasks.

Any other arrangement that gives a large task to a slower processor can only increase the overall maximum completion time. This exchange argument guarantees the greedy arrangement is optimal.

Python Solution

from typing import List

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()
        tasks.sort(reverse=True)

        answer = 0

        for i in range(len(processorTime)):
            completion_time = processorTime[i] + tasks[i * 4]
            answer = max(answer, completion_time)

        return answer

The implementation begins by sorting the processors in ascending order and the tasks in descending order.

Because each processor receives exactly 4 tasks, we can process processors one by one. For processor i, the tasks assigned are conceptually:

tasks[i * 4 : i * 4 + 4]

Since the tasks are sorted descending, the largest task in this group is always tasks[i * 4].

The completion time for that processor is therefore:

processorTime[i] + tasks[i * 4]

We compute this value for every processor and maintain the largest value seen. That largest value is the overall finishing time for all tasks.

The implementation is concise because the greedy observation eliminates the need for complicated data structures.

Go Solution

package main

import (
	"sort"
)

func minProcessingTime(processorTime []int, tasks []int) int {
	sort.Ints(processorTime)

	sort.Slice(tasks, func(i, j int) bool {
		return tasks[i] > tasks[j]
	})

	answer := 0

	for i := 0; i < len(processorTime); i++ {
		completionTime := processorTime[i] + tasks[i*4]

		if completionTime > answer {
			answer = completionTime
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

One important difference is sorting tasks in descending order. Go's sort.Ints() only sorts ascending, so we use sort.Slice() with a custom comparator.

Go uses explicit loops and manual maximum comparison instead of Python's built in max() function.

Integer overflow is not an issue because:

processorTime[i] <= 1e9
tasks[i] <= 1e9

Their sum fits safely within Go's 64 bit integer range, and also within signed 32 bit range since the maximum possible value is 2e9.

Worked Examples

Example 1

Input:

processorTime = [8, 10]
tasks = [2, 2, 3, 1, 8, 7, 4, 5]

Step 1: Sort processors ascending

processorTime = [8, 10]

Already sorted.

Step 2: Sort tasks descending

tasks = [8, 7, 5, 4, 3, 2, 2, 1]

Step 3: Assign tasks

Processor Index	Processor Time	Assigned Tasks	Largest Task	Completion Time
0	8	[8, 7, 5, 4]	8	16
1	10	[3, 2, 2, 1]	3	13

Step 4: Compute final answer

max(16, 13) = 16

Output:

Example 2

Input:

processorTime = [10, 20]
tasks = [2, 3, 1, 2, 5, 8, 4, 3]

Step 1: Sort processors ascending

processorTime = [10, 20]

Step 2: Sort tasks descending

tasks = [8, 5, 4, 3, 3, 2, 2, 1]

Step 3: Assign tasks

Processor Index	Processor Time	Assigned Tasks	Largest Task	Completion Time
0	10	[8, 5, 4, 3]	8	18
1	20	[3, 2, 2, 1]	3	23

Step 4: Compute final answer

max(18, 23) = 23

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log m)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation

The algorithm spends almost all its time sorting the two arrays.

If n is the number of processors and m is the number of tasks:

Sorting processors costs O(n log n)
Sorting tasks costs O(m log m)
The final traversal is linear

Since m = 4n, the complexity can also be viewed as:

O(m log m)

The extra space depends on the language's sorting implementation. The algorithm itself only uses a few variables.

Test Cases

from typing import List

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()
        tasks.sort(reverse=True)

        answer = 0

        for i in range(len(processorTime)):
            answer = max(answer, processorTime[i] + tasks[i * 4])

        return answer

solution = Solution()

# Example 1 from problem statement
assert solution.minProcessingTime(
    [8, 10],
    [2, 2, 3, 1, 8, 7, 4, 5]
) == 16

# Example 2 from problem statement
assert solution.minProcessingTime(
    [10, 20],
    [2, 3, 1, 2, 5, 8, 4, 3]
) == 23

# Single processor, simplest valid case
assert solution.minProcessingTime(
    [5],
    [1, 2, 3, 4]
) == 9

# All processors identical
assert solution.minProcessingTime(
    [5, 5],
    [1, 2, 3, 4, 5, 6, 7, 8]
) == 13

# All tasks identical
assert solution.minProcessingTime(
    [1, 10],
    [5, 5, 5, 5, 5, 5, 5, 5]
) == 15

# Large processor difference
assert solution.minProcessingTime(
    [1, 100],
    [1, 2, 3, 100, 4, 5, 6, 7]
) == 107

# Already sorted input
assert solution.minProcessingTime(
    [1, 2],
    [8, 7, 6, 5, 4, 3, 2, 1]
) == 9

# Reverse sorted processors
assert solution.minProcessingTime(
    [20, 5],
    [1, 2, 3, 4, 5, 6, 7, 8]
) == 24

# Minimum values
assert solution.minProcessingTime(
    [0],
    [1, 1, 1, 1]
) == 1

# Large values
assert solution.minProcessingTime(
    [10**9],
    [10**9, 10**9, 10**9, 10**9]
) == 2 * 10**9

Test Summary

Test	Why
Example 1	Validates standard mixed input
Example 2	Validates another official scenario
Single processor	Smallest valid input
All processors identical	Ensures task assignment still matters
All tasks identical	Confirms processor ordering dominates
Large processor difference	Tests greedy balancing
Already sorted input	Ensures algorithm handles pre sorted arrays
Reverse sorted processors	Confirms sorting is necessary
Minimum values	Tests smallest numeric constraints
Large values	Verifies no overflow issues

Edge Cases

One important edge case is when there is only a single processor. In this scenario, all four tasks must go to that processor regardless of ordering. A buggy implementation might still attempt complicated balancing logic, but the correct answer is simply:

processorTime[0] + max(tasks)

The implementation naturally handles this because the loop runs once and uses tasks[0] after descending sort.

Another important case occurs when processor availability times vary dramatically. For example:

processorTime = [1, 100]

If the largest task is incorrectly assigned to the slower processor, the total completion time becomes unnecessarily large. The greedy sorting strategy prevents this by always pairing the earliest processor with the largest tasks.

A third edge case is when all task durations are equal. In this situation, task assignment no longer matters because every processor receives the same maximum task duration. The only thing affecting the answer is processor availability time. The implementation still works correctly because sorting identical values changes nothing.

A final subtle case is when the input arrays are already sorted in the opposite direction of what we need. If we forget to sort processors ascending and tasks descending, the greedy strategy fails. The implementation explicitly sorts both arrays before assignment, guaranteeing consistent behavior regardless of input order.