Skip to content

LeetCode: 2244-Minimum Rounds to Complete All Tasks 解題紀錄

Last Updated on 2023-01-04 by Clay

題目

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

題目給定一串數值陣列,陣列中的每個元素都代表一個指定難度的任務。我們每個回合只能解同一種類型的任務,每次可以解 2 個或是 3 個同種任務。

我們要計算的是,最少要花多少回合,才能把所有任務解決掉呢?如果有無法解決的情況,則回傳 -1


解題思路

哈希表(Hash Table)

  1. 我們可以使用哈希表來儲存每種種類的任務有多少個。
  2. 針對每種特定種類的任務,我們先判斷是否能被 3 整除。這時候會分成兩種情況
    • 被 3 整除:代表最少的解決回合數即為『任務數除以 3
    • 不被 3 整除:無論是餘 1 還是餘 2,最少的解決回合數都是『任務數除以 3 加 1
  3. 把所有任務的最少解決回合數加總,即為我們要的答案;如果中途有任何一種特定任務的數量為 1,則代表我們無論如何都解決不了,所以回傳 -1


哈希表 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


C++ 範例程式碼

class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        // Init
        int rounds = 0;
        unordered_map<int, int> mp;
        for (int& task: tasks) {
            ++mp[task];
        }

        // Count `rounds`
        for (auto& it: mp) {
            if (it.second == 1) {
                return -1;
            }

            rounds += it.second % 3 ? it.second / 3 + 1 : it.second / 3;
        }

        return rounds;
    }
};



Python 範例程式碼

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        # Init
        rounds = 0
        mp = {}
        for task in tasks:
            mp[task] = mp.get(task, 0) + 1

        # Count `rounds`
        for key in mp:
            if mp[key] == 1:
                return -1
            rounds += mp[key] // 3 + 1 if mp[key] % 3 else mp[key] // 3

        return rounds

References


Read More

Leave a Reply