#2895

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Processing Time

Determine the minimum total processing time by optimally assigning tasks to multiple processors using a greedy approach.

array greedy sorting

Problem Statement

You are given a set of processors, each with 4 cores, and a list of tasks where the total number of tasks equals four times the number of processors. Each task must run on a separate core, and no core can execute more than one task at a time.

Given an array processorTime representing the time each processor is available and an array tasks representing task durations, return the minimum total time required to complete all tasks. Each processor can run up to 4 tasks simultaneously on its cores, and the goal is to schedule tasks so the latest finishing processor completes as early as possible.

Examples

Example 1

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

Output: 16

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

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

Solution Approach

Sort processors and tasks

Begin by sorting the processorTime array in ascending order and the tasks array in descending order. This sets up the greedy assignment pattern where the earliest available processor gets the longest remaining tasks, maintaining the invariant that no processor finishes unnecessarily late.

Assign tasks in blocks of four

Iterate through the sorted processorTime list, assigning each processor a block of four tasks from the sorted tasks array. Compute each processor's finish time as the maximum of its availability plus assigned task durations. This step ensures the greedy choice is consistently applied to minimize the overall completion time.

Compute final minimum processing time

After all tasks are assigned, the minimum processing time is the maximum finish time across all processors. This approach guarantees that the invariant of assigning longer tasks to earlier processors holds, preventing inefficient schedules and reducing overall completion time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting processors and tasks takes O(n log n) for n processors and O(m log m) for m tasks. Assigning tasks in blocks of four is O(n). Space complexity is O(n + m) for storing sorted arrays.

What Interviewers Usually Probe

Do you recognize that this is a greedy choice plus invariant validation problem?
Can you explain why sorting tasks descending and processors ascending ensures minimal maximum time?
How do you handle the fixed block size of 4 tasks per processor in your schedule?

Common Pitfalls or Variants

Common pitfalls

Failing to sort tasks in descending order can result in suboptimal schedules with higher maximum completion time.
Ignoring the processor's initial availability can cause incorrect calculations of finish times.
Not respecting the 4-task per processor limit can produce invalid assignments.

Follow-up variants

Allow processors with different core counts, requiring dynamic block sizes for assignments.
Introduce task dependencies that prevent certain tasks from running simultaneously on the same processor.
Minimize total idle time instead of maximum finish time, shifting the greedy pattern slightly.

FAQ

What is the key pattern to solve Minimum Processing Time efficiently?

The problem follows a greedy choice plus invariant validation pattern where early processors take longer tasks to minimize the maximum finish time.

Why must tasks be sorted in descending order?

Sorting tasks ensures that the longest tasks are assigned to the earliest available processors, maintaining the invariant that maximum completion time is minimized.

Can a processor handle more than 4 tasks?

No, each processor has exactly 4 cores, and each core can execute only one task at a time, making the 4-task block assignment essential.

How do I compute the minimum processing time after assignment?

After assigning tasks in blocks of four to each processor, compute each processor's finish time and take the maximum across all processors.

What common mistakes increase processing time in this problem?

Typical errors include ignoring processor availability, not sorting tasks descending, or exceeding the 4-task limit per processor, all leading to suboptimal schedules.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()
        tasks.sort()
        ans = 0
        i = len(tasks) - 1
        for t in processorTime:
            ans = max(ans, t + tasks[i])
            i -= 4
        return ans

Continue Practicing

#2931 maximum spending after buying items #2952 minimum number of coins to be added #2966 divide array into arrays with max difference