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.

#2895

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最小处理时间

你有 n 颗处理器，每颗处理器都有 4 个核心。现有 n * 4 个待执行任务，每个核心只执行一次任务。给你一个下标从 0 开始的整数数组 processorTime ，表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks ，表示执行每个任务所需的时间。返回所有任务都执…

数组贪心排序

题目描述

你有 n 颗处理器，每颗处理器都有 4 个核心。现有 n * 4 个待执行任务，每个核心只执行一次任务。

给你一个下标从 0 开始的整数数组 processorTime ，表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 最小时间 。

注意：每个核心独立执行任务。

示例 1：

输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。 
第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。
第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。
因此，可以证明执行完所有任务需要花费的最小时间是 16 。

示例 2：

输入：processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
输出：23
解释：
最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器（最早空闲时间 time = 10），下标为 0, 2, 3, 7 的任务分配给第二颗处理器（最早空闲时间 time = 20）。 
第一颗处理器执行完所有任务需要花费的时间 = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18 。 
第二颗处理器执行完所有任务需要花费的时间 = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23 。 
因此，可以证明执行完所有任务需要花费的最小时间是 23 。

提示：

1 <= n == processorTime.length <= 25000
1 <= tasks.length <= 10⁵
0 <= processorTime[i] <= 10⁹
1 <= tasks[i] <= 10⁹
tasks.length == 4 * n

lightbulb

解题思路

方法一：贪心 + 排序

要使得处理完所有任务的时间最小，那么越早处于空闲状态的处理器应该处理耗时最长的 $4$ 个任务。

因此，我们对处理器的空闲时间和任务的耗时分别进行排序，然后依次将耗时最长的 $4$ 个任务分配给空闲时间最早的处理器，计算最大的结束时间即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为任务的数量。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2931 购买物品的最大开销 #2952 需要添加的硬币的最小数量 #2966 划分数组并满足最大差限制