---
title: "2244. Minimum Rounds to Complete All Tasks"
url: "https://laigary.com/interview/coding/2244-minimum-rounds-to-complete-all-tasks"
type: "note"
section: "coding"
date: "2025-10-25"
updated: "2026-07-27"
tags: ["Greedy", "Dynamic Programming", "Hash Table"]
---

# 2244. Minimum Rounds to Complete All Tasks

[2244\. Minimum Rounds to Complete All Tasks](https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/)

這一題可以算是經典的 [Dynamic Programming](/interview/coding?tag=Dynamic%20Programming) [70\. Climbing Stairs](/interview/coding/70-climbing-stairs) 的變形。只是題目從一次可以走一階兩階，變成了一次可以走兩階或三階，但是要考慮無法走完的情況。

```python
class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        
        counter = Counter(tasks)

        @cache
        def dp(jobs):
            if jobs == 0:
                return 0
            if jobs == 1:
                return -1
            if jobs == 2 or jobs == 3:
                return 1
            
            two = dp(jobs - 2)
            three = dp(jobs - 3)
            if two == -1 and three == -1:
                return -1
            elif two == -1:
                return 1 + three
            elif three == -1:
                return 1 + two
            else:
                return 1 + min(two, three)

        count = 0
        for values in counter.values():
            curr = dp(values)
            if curr == -1:
                return -1
            count += curr

        return count
```

時間複雜度的分析比較複雜一點 。

1.  我們需要 $O(n)$ 的時間複雜度去計算出 tasks 的計數
2.  遞迴的部分，我們有使用了記憶體優化的方法，所以總共會計算 $ O(M) $ 次，$M = max(counter.values())$，因為我們只會計算出 0 至 M 的 dp 一次。
3.  最後是我們會對每一個任務呼叫一次 dp ，總共會計算 $O(k)$ 次，$k = len(counter.values())$。

最後的時間複雜度是 $O(n + M + k) ~= O(n) $ 空間複雜度也是 $O(n)$。

## 貪心：這個 DP 有封閉解

回頭看 `dp(jobs)` 到底在做什麼：把 `jobs` 拆成若干個 2 和 3，讓份數最少。這件事不需要遞迴，可以直接算出來。

設拆成 $a$ 個 2 和 $b$ 個 3，也就是 $2a + 3b = c$，要最小化 $a + b$。既然每一份最多只能吃 3 個，份數的**下界**就是 $\lceil c/3 \rceil$。而這個下界在 $c \ge 2$ 時**永遠達得到**，分三種情況檢查：

- $c \equiv 0 \pmod 3$：全部用 3，共 $c/3$ 份
- $c \equiv 1 \pmod 3$：拿一個 3 跟落單的 1 湊成兩個 2（$3 + 1 \to 2 + 2$），共 $(c-4)/3 + 2 = \lceil c/3 \rceil$ 份
- $c \equiv 2 \pmod 3$：剩下的 2 自己一份，共 $(c-2)/3 + 1 = \lceil c/3 \rceil$ 份

唯一的例外是 $c = 1$ —— 1 湊不出任何 2 和 3 的組合，直接回 -1。

```python
class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        ans = 0
        for count in Counter(tasks).values():
            if count == 1:
                return -1
            ans += (count + 2) // 3
        return ans
```

`(count + 2) // 3` 就是 $\lceil count/3 \rceil$ 的整數寫法。

### 貪在哪裡

貪心的動作是：**每一份都盡量吃 3 個。**

它安全是因為上面那個下界論證 —— 份數不可能少於 $\lceil c/3 \rceil$，而「盡量吃 3」正好達到這個值，所以它就是最佳解。既然如此，就不必在每一步去試「這一份要吃 2 還是吃 3」，DP 的那個 `min(two, three)` 是白算的。

另外值得留意的是**為什麼整題可以拆開算**：不同難度的任務不能放在同一份裡，所以 $k$ 種難度就是 $k$ 個互不影響的子問題，各自求最小值再相加即可。如果題目允許同一份混不同難度，這個拆解立刻垮掉，就得回去用 DP 了。

## 補充

同樣是「DP 想得出來，但其實有封閉解 / 貪心解」的題：[1323. Maximum 69 Number](/interview/coding/1323-maximum-69-number)（改最左邊那個 6 就好）、[2126. Destroying Asteroids](/interview/coding/2126-destroying-asteroids)（排序後由小吃到大）。判斷方式見 [Greedy 模板](/interview/coding/greedy-template)。

## 複雜度

- 時間 $O(n)$ — 一次計數 $O(n)$，再掃過 $k$ 種難度，$k \le n$
- 空間 $O(k)$ — Counter 的大小

其中 $n$ 是 `tasks` 的長度、$k$ 是相異難度的數量。跟 DP 版本的差別在於省掉了 $O(M)$ 的記憶化表（$M$ 是最大的出現次數），以及遞迴的呼叫堆疊。