Medium

题目描述

你有若干个处理器，每个处理器有 4 个核心。要执行的任务数量是处理器数量的四倍。每个任务必须分配给唯一的核心，且每个核心只能使用一次。

给你一个数组 processorTime 表示每个处理器变为可用的时间，以及一个数组 tasks 表示每个任务完成所需的时间。返回完成所有任务所需的最少时间。

示例 1：

输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
将索引为 4, 5, 6, 7 的任务分配给第一个处理器（在时间 = 8 时变为可用），将索引为 0, 1, 2, 3 的任务分配给第二个处理器（在时间 = 10 时变为可用）。
第一个处理器完成所有任务的时间是 max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16。
第二个处理器完成所有任务的时间是 max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13。

示例 2：

输入：processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
输出：23
解释：
将索引为 1, 4, 5, 6 的任务分配给第一个处理器，其余任务分配给第二个处理器。
第一个处理器完成所有任务的时间是 max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18。
第二个处理器完成所有任务的时间是 max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23。

约束条件：

  • 1 <= n == processorTime.length <= 25000
  • 1 <= tasks.length <= 10^5
  • 0 <= processorTime[i] <= 10^9
  • 1 <= tasks[i] <= 10^9
  • tasks.length == 4 * n

解题思路

解题思路

这是一个贪心算法问题。我们需要最小化所有处理器中最大的完成时间。

核心思想：

  • 每个处理器有4个核心，可以同时执行4个任务
  • 处理器的总完成时间是其开始时间加上分配给它的最长任务时间
  • 为了最小化最大完成时间，我们应该让较早可用的处理器执行较长的任务

贪心策略：

  1. 对处理器按可用时间升序排序
  2. 对任务按执行时间降序排序
  3. 依次将最长的4个任务分配给最早可用的处理器，次长的4个任务分配给次早可用的处理器，以此类推
  4. 每个处理器的完成时间是其可用时间加上分配给它的最长任务时间
  5. 返回所有处理器中的最大完成时间

这样分配的原因是：较早可用的处理器有更多时间来处理长任务，而较晚可用的处理器处理短任务不会显著增加总时间。通过这种匹配，我们可以平衡各处理器的负载，从而最小化整体完成时间。

推荐解法： 贪心 + 排序，时间复杂度最优。

代码实现

class Solution {
public:
    int minProcessingTime(vector<int>& processorTime, vector<int>& tasks) {
        sort(processorTime.begin(), processorTime.end());
        sort(tasks.begin(), tasks.end(), greater<int>());
        
        int result = 0;
        for (int i = 0; i < processorTime.size(); i++) {
            int maxTime = processorTime[i] + tasks[i * 4];
            result = max(result, maxTime);
        }
        
        return result;
    }
};

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime.sort()
        tasks.sort(reverse=True)
        
        result = 0
        for i in range(len(processorTime)):
            max_time = processorTime[i] + tasks[i * 4]
            result = max(result, max_time)
            
        return result

public class Solution {
    public int MinProcessingTime(IList<int> processorTime, IList<int> tasks) {
        var processors = processorTime.ToArray();
        var taskArray = tasks.ToArray();
        
        Array.Sort(processors);
        Array.Sort(taskArray, (a, b) => b.CompareTo(a));
        
        int result = 0;
        for (int i = 0; i < processors.Length; i++) {
            int maxTime = processors[i] + taskArray[i * 4];
            result = Math.Max(result, maxTime);
        }
        
        return result;
    }
}

var minProcessingTime = function(processorTime, tasks) {
    processorTime.sort((a, b) => a - b);
    tasks.sort((a, b) => b - a);
    
    let result = 0;
    for (let i = 0; i < processorTime.length; i++) {
        let maxTime = processorTime[i] + tasks[i * 4];
        result = Math.max(result, maxTime);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m log m)其中 n 是处理器数量，m 是任务数量。主要开销在排序操作上
空间复杂度O(1)只使用常数额外空间（不考虑排序的空间开销）