最小处理时间

标签: 贪心 数组 排序

难度: Medium

你有 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 <= 105
  • 0 <= processorTime[i] <= 109
  • 1 <= tasks[i] <= 109
  • tasks.length == 4 * n

Submission

运行时间: 92 ms

内存: 31.0 MB

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()
        tasks.sort(reverse=True)
        return max(p+t for p, t in zip(processorTime, tasks[::4]))

Explain

此题的核心思想是贪心算法。通过将处理器的空闲时间从小到大排序，并将任务所需时间从大到小排序，可以实现最优的任务调度。排序后，将最长的任务分配给最早空闲的处理器，然后每个处理器分配到的第一个任务是它能接受的最大任务。代码中利用zip函数组合处理器和任务数组，通过每四个任务选择一个，确保每个处理器在同一时间只处理一个任务。最后，通过计算每个处理器完成其任务的时间，并取最大值，就能得到所有任务完成所需的最小时间。

时间复杂度: O(n log n)

空间复杂度: O(log n)

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()  # 将处理器的空闲时间从小到大排序
        tasks.sort(reverse=True)  # 将任务的执行时间从大到小排序
        # 使用zip组合处理器和任务，并计算每个处理器完成其任务的时间
        # 每个处理器只取间隔为4的任务，确保任务分配的公平性
        return max(p+t for p, t in zip(processorTime, tasks[::4]))

Explore

通过将`processorTime`数组升序排序，可以确保我们首先分配任务给最早空闲的处理器，从而尽快开始任务的处理。而将`tasks`数组进行降序排序，则可以确保最耗时的任务尽可能早地得到处理，这有助于减少等待时间，使得处理器在处理完其当前任务后，可以立即接手下一项较大的任务，最终实现整体任务完成时间的最小化。这种方法是典型的贪心策略，通过局部最优的选择（最早空闲处理器与最长任务的匹配）来达到全局最优。

此处选择每四个任务取一个，是基于每个处理器拥有四个核心，每核心执行一个任务的假设。通过选择`tasks[::4]`是为了确保每个处理器在同一时间只接受一个任务。错误理解了题意，题目实际上要求每个核心处理一个任务，而代码中的方法将每四个任务中的最大任务分配给一个处理器，这会导致每个处理器只处理一个任务而非四个，因此会造成资源的浪费。正确的方法应该是每个处理器分配四个任务，而不是通过`tasks[::4]`这种方式。

题解中的代码实际上没有正确处理每个核心只执行一个任务的要求。正确的方式应该是确保每个处理器的每个核心分别分配到一个任务。题解中的方法误用了`tasks[::4]`，导致每个处理器只分配到每四个任务中的最大一个，没有充分利用处理器的四个核心。正确的做法应该是，对于每个处理器，应从任务列表中分配四个任务，每个核心执行一个任务。这需要重新设计任务分配策略，以确保每个核心的独立工作，而不仅仅是每个处理器。