2244. 完成所有任务需要的最少轮数

题目

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

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

示例 1：

输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要想完成所有任务，一个可能的计划是：

• 第一轮，完成难度级别为 2 的 3 个任务。
• 第二轮，完成难度级别为 3 的 2 个任务。
• 第三轮，完成难度级别为 4 的 3 个任务。
• 第四轮，完成难度级别为 4 的 2 个任务。
  可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-rounds-to-complete-all-tasks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

统计每个难度的次数，然后遍历累加每种任务所需次数，如果有一种难度的任务个数为1，则返回-1。对于某一类难度次数，如果为3的倍数，则需要次，否则可能包含两种情况，余数为1，分出一个3拆成两个2，余数为2，直接加一次，这两种情况都是需要次。总的汇总起来，其实就是除以3向上取整。

代码

java

class Solution {
    public int minimumRounds(int[] tasks) {
        int n = tasks.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int t : tasks) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        int ans = 0;
        for (int cnt : map.values()) {
            if (cnt == 1) {
                return -1;
            }
            // (cnt + 2) / 3 是cnt除以3向上取整，也可以写做 (cnt - 1) 
            ans += (cnt + 2) / 3;
        }
        return ans;
    }
}

py3

python也太简洁了…

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        c = Counter(tasks)
        ans = 0
        for t in c:
            if c[t] == 1:
                return -1
            ans += (c[t] + 2) // 3
        return ans