Medium

题目描述

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。

请你返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。

示例 1：

输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要完成所有任务，一个可能的计划是：
- 第一轮，你完成 3 个难度级别为 2 的任务。 
- 第二轮，你完成 2 个难度级别为 3 的任务。
- 第三轮，你完成 3 个难度级别为 4 的任务。
- 第四轮，你完成 2 个难度级别为 4 的任务。
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。

示例 2：

输入：tasks = [2,3,3]
输出：-1
解释：只有 1 个难度级别为 2 的任务，但每一轮中，你只能完成 2 个或者 3 个相同难度级别的任务。因此，你无法完成所有任务，答案为 -1 。

提示：

  • 1 <= tasks.length <= 10^5
  • 1 <= tasks[i] <= 10^9

解题思路

这道题的核心是贪心算法。我们需要统计每个难度级别的任务数量，然后计算完成这些任务所需的最少轮数。

关键观察：

  1. 每轮只能完成2个或3个相同难度的任务
  2. 如果某个难度级别只有1个任务，则无法完成（返回-1）
  3. 对于n个相同难度的任务，我们要找到最少轮数

贪心策略： 对于n个任务，我们优先使用3个任务一轮的方式，因为这样效率更高：

  • 如果 n % 3 == 0，则需要 n/3 轮
  • 如果 n % 3 == 1，则最后4个任务用两轮完成（2+2），总共需要 (n-4)/3 + 2 = (n+2)/3 轮
  • 如果 n % 3 == 2，则最后2个任务用一轮完成，总共需要 n/3 + 1 = (n+2)/3 轮

可以发现，当n >= 2时，最少轮数总是 (n + 2) / 3。

算法步骤：

  1. 使用哈希表统计每个难度级别的任务数量
  2. 遍历每个难度级别，检查是否可以完成（数量>=2）
  3. 累加每个难度级别所需的最少轮数

代码实现

class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        unordered_map<int, int> count;
        for (int task : tasks) {
            count[task]++;
        }
        
        int rounds = 0;
        for (auto& [difficulty, freq] : count) {
            if (freq == 1) {
                return -1;
            }
            rounds += (freq + 2) / 3;
        }
        
        return rounds;
    }
};

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        count = Counter(tasks)
        
        rounds = 0
        for freq in count.values():
            if freq == 1:
                return -1
            rounds += (freq + 2) // 3
        
        return rounds

public class Solution {
    public int MinimumRounds(int[] tasks) {
        var count = new Dictionary<int, int>();
        foreach (int task in tasks) {
            count[task] = count.GetValueOrDefault(task, 0) + 1;
        }
        
        int rounds = 0;
        foreach (int freq in count.Values) {
            if (freq == 1) {
                return -1;
            }
            rounds += (freq + 2) / 3;
        }
        
        return rounds;
    }
}

/**
 * @param {number[]} tasks
 * @return {number}
 */
var minimumRounds = function(tasks) {
    const freq = new Map();
    
    for (const task of tasks) {
        freq.set(task, (freq.get(task) || 0) + 1);
    }
    
    let rounds = 0;
    
    for (const count of freq.values()) {
        if (count === 1) return -1;
        rounds += Math.ceil(count / 3);
    }
    
    return rounds;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次进行计数，然后遍历哈希表一次计算轮数
空间复杂度O(k)k为不同难度级别的数量，最坏情况下为O(n)

相关题目