Question

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

English Version

题目描述

给你一个下标从 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 <= 105
• 1 <= tasks[i] <= 109

解法

方法一：哈希表

我们用哈希表统计每个难度级别的任务数量，然后遍历哈希表，对于每个难度级别的任务数量，如果数量为 $1$，则无法完成所有任务，返回 $-1$；否则，计算完成该难度级别的任务需要的轮数，累加到答案中。

最后返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 tasks 的长度。

class Solution:
  def minimumRounds(self, tasks: List[int]) -> int:
    cnt = Counter(tasks)
    ans = 0
    for v in cnt.values():
      if v == 1:
        return -1
      ans += v // 3 + (v % 3 != 0)
    return ans

class Solution {
  public int minimumRounds(int[] tasks) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int t : tasks) {
      cnt.merge(t, 1, Integer::sum);
    }
    int ans = 0;
    for (int v : cnt.values()) {
      if (v == 1) {
        return -1;
      }
      ans += v / 3 + (v % 3 == 0 ? 0 : 1);
    }
    return ans;
  }
}

class Solution {
public:
  int minimumRounds(vector<int>& tasks) {
    unordered_map<int, int> cnt;
    for (auto& t : tasks) {
      ++cnt[t];
    }
    int ans = 0;
    for (auto& [_, v] : cnt) {
      if (v == 1) {
        return -1;
      }
      ans += v / 3 + (v % 3 != 0);
    }
    return ans;
  }
};

func minimumRounds(tasks []int) int {
  cnt := map[int]int{}
  for _, t := range tasks {
    cnt[t]++
  }
  ans := 0
  for _, v := range cnt {
    if v == 1 {
      return -1
    }
    ans += v / 3
    if v%3 != 0 {
      ans++
    }
  }
  return ans
}

function minimumRounds(tasks: number[]): number {
  const cnt = new Map();
  for (const t of tasks) {
    cnt.set(t, (cnt.get(t) || 0) + 1);
  }
  let ans = 0;
  for (const v of cnt.values()) {
    if (v == 1) {
      return -1;
    }
    ans += Math.floor(v / 3) + (v % 3 === 0 ? 0 : 1);
  }
  return ans;
}