作者:
Rushia (みけねこ的鼻屎)
2023-01-04 10:00:482244. 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: