推 pandix: 大師 01/04 10:01
推 Jaka: 大師 01/04 10:04
2244. Minimum Rounds to Complete All Tasks
給你一個陣列tasks表示一堆任務，task[i]表示第i個任務的難度，我們每一輪可以
完成2~3個同一種難度的任務，求出最少幾輪可以完成所有任務，若無法完成所有任
務則返回-1。
Example：
Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation:
第一輪可以做3個難度2的任務
第二輪可以做2個難度3的任務
第三輪可以做3個難度4的任務
第四輪可以做2個難度4的任務
最少需做四輪
Input: tasks = [2,3,3]
Output: -1
Explanation:
第一輪可以做兩個難度3的任務
第二輪只剩下一個難度1的任務所以無法做完。
思路：
1.先用一個map統計所有難度的任務的出現次數。
2.遍歷每個難度的次數，如果次數為1表示當前難度無法完成直接返回-1。
3.因為我們要求最小輪次，所以我們要盡可能的在每一輪完成最多任務
（換句話說就是盡可能的每輪都完成三次任務），對每輪可以完成的任務
次數進行貪婪，分兩個case：
(1)若次數可以被三整除，則每輪都做三個任務會是最小次數。
9 = 3 + 3 + 3
(2)若次數不被三整除，則每一輪都做三個任務且最後一輪改成做兩個任務兩輪
即是最小次數。
7 = 3 + [3] => 3 + [2 + 2]
4.將每種難度的最小次數累加後返回之。
Java Code：
----------------------------------
class Solution {
public int minimumRounds(int[] tasks) {
int rounds = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int task : tasks) {
map.put(task, map.getOrDefault(task, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int amount = entry.getValue();
if (amount < 2) {
return -1;
} else if (amount % 3 == 0) {
rounds += amount/3;
} else {
rounds += amount/3 + 1;
}
}
return rounds;
}
}
----------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.71.48 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672797651.A.970.html