🔗 🟡 2244. Minimum Rounds to Complete All Tasks 1372

tags: `Weekly Contest 289` `貪心(Greedy)` `計數(Counter)`

題意

給定一個下標從 $0$ 開始的整數陣列 $tasks$ ，其中 $tasks[i]$ 表示任務的難度，在每一回合中，可以完成 $2$ 個或 $3$ 個相同難度的任務。

返回完成所有任務所需要的最小回合數，如果無法完成所有任務，則返回 $-1$ 。

思路：貪心(Greedy) + 計數(Counter)

首先，由於我們每次完成的任務難度必須是相同的，所以我們可以先用 Counter 計算每個難度的任務數量 $v$ ，接著對不同難度的任務，考慮 $v$ 即可。

再來想一下，何時無法完成任務，先把範圍縮小到 $[1, 6]$ ，可以發現只有當 $v=1$ 時無法完成任務；接著放大範圍到 $v > 6$ ，假定每次都完成 $3$ 個任務，則可以根據 $v \pmod 3$ 的不同情況考慮：

若 $v \pmod 3 = 0$ ，則 $v$ 可以被 $3$ 整除，每次完成 $3$ 個任務，所以需要 $v/3$ 回合；
若 $v \pmod 3 = 1$ ，則可以完成 $\lfloor v/3 \rfloor$ 輪 $3$ 個任務，但還剩下 $1$ 個任務。不過我們可以將其中 $1$ 輪的 $3$ 個任務，結合剩下的 $1$ 個任務，置換成 $2$ 輪完成 $2$ 個任務，所以需要 $\lfloor v/3 \rfloor - 2 + 1 = \lfloor v/3 \rfloor + 1$ 回合；
若 $v \pmod 3 = 2$ ，則可以完成 $\lfloor v/3 \rfloor$ 輪 $3$ 個任務，剩下的 $2$ 個任務需要 $1$ 輪完成，所以需要 $\lfloor v/3 \rfloor + 1$ 回合。
以上三種情況可以合併成 $\lfloor v/3 \rfloor + (v \pmod 3 \neq 0)$ 回合，因此我們只要檢查 $v = 1$ 的情況即可。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(n)$

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(vector<int>& tasks) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (int x : tasks) cnt[x]++;
        for (auto kv : cnt) {
            int v = kv.second;
            if (v == 1) return -1;
            ans += v / 3 + (v % 3 ? 1 : 0);
        }
        return ans;
    }
};