[LeetCode] 2244. Minimum Rounds to Complete All Tasks

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.

Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Example 1:
Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation: To complete all the tasks, a possible plan is:

  • In the first round, you complete 3 tasks of difficulty level 2.
  • In the second round, you complete 2 tasks of difficulty level 3.
  • In the third round, you complete 3 tasks of difficulty level 4.
  • In the fourth round, you complete 2 tasks of difficulty level 4.
    It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.

Example 2:
Input: tasks = [2,3,3]
Output: -1
Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.

Constraints:
1 <= tasks.length <= 105
1 <= tasks[i] <= 109

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

给你一个下标从 0 开始的整数数组 tasks ,其中 tasks[i] 表示任务的难度级别。在每一轮中,你可以完成 2 个或者 3 个 相同难度级别 的任务。 返回完成所有任务需要的 最少 轮数,如果无法完成所有任务,返回 -1 。 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/minimum-rounds-to-complete-all-tasks 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

不难想到是需要用 hashmap 先统计一下 每个不同难度级别的任务 分别出现了几次(key, c),然后再计算 每个不同难度级别的任务 需要几轮才能完成。计算轮数的时候,涉及到一些数学/归纳。我这里提供一个分类讨论的办法,不是最优解,写的有点麻烦。

  • c = 1,直接返回 -1,因为不能处理
  • c = 2,因为可以被 2 整除,所以次数 = c / 2
  • 从 c = 3 开始
    • 如果 c = 3k,等同于 c % 3 == 0,那么次数 = k
    • 如果 c = 3k + 1,等同于 c % 3 == 1,把他替换成 c = 3k + 1 - 4 = 3k - 3 = 3(k - 1),然后 4 还是要被 2 处理两次,所以最终次数 = k - 1 + 2 = k + 1
    • 如果 c = 3k + 2,等同于 c % 3 == 2,那么次数 = k + 1

复杂度

时间O(n)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int minimumRounds(int[] tasks) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int t : tasks) {
map.put(t, map.getOrDefault(t, 0) + 1);
}

int res = 0;
for (int key : map.keySet()) {
int count = map.get(key);
if (count == 1) {
return -1;
} else if (count == 2) {
res++;
} else if (count % 3 == 0) {
res += count / 3;
} else if (count % 3 == 1) {
res += (count - 4) / 3 + 2;
} else if (count % 3 == 2) {
res += (count - 2) / 3 + 1;
}
}
return res;
}
}

[LeetCode] 2244. Minimum Rounds to Complete All Tasks
https://shurui91.github.io/posts/3323451786.html
Author
Aaron Liu
Posted on
January 4, 2023
Licensed under