# Minimum Rounds to Complete All Tasks
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks)
Canonical: https://scaleengineer.com/dsa/problems/minimum-rounds-to-complete-all-tasks
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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`

**Note:** This question is the same as [2870: Minimum Number of Operations to Make Array Empty.](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/description/)

# Approaches
## Sorting and Iteration
This approach first sorts the input array. By sorting, all tasks of the same difficulty level become adjacent. We can then iterate through the sorted array once to count the occurrences of each task difficulty and calculate the rounds required.
**Time:** O(N log N), dominated by the sorting step. The subsequent scan of the array takes O(N) time. · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm implementation. For example, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
**Pros:** Conceptually simple if you are familiar with sorting.; Doesn't require an auxiliary data structure like a hash map, potentially saving space if the sorting is in-place or has low space overhead.
**Cons:** The O(N log N) time complexity is suboptimal for this problem.
### Explanation
The core idea is to group identical tasks together. Sorting is a straightforward way to achieve this. After sorting `tasks`, we can iterate from the beginning. We'll use a variable, say `count`, to keep track of the number of consecutive identical tasks. We traverse the array, and as long as the current task is the same as the previous one, we increment `count`. When we encounter a different task or reach the end of the array, it signifies the end of a group of identical tasks. At this point, we have the `count` for a specific difficulty level. We first check if `count` is 1. If it is, completing the tasks is impossible, so we return -1. Otherwise, we need to find the minimum rounds to complete `count` tasks. We can use groups of 2 or 3. To minimize the number of rounds, we should maximize the use of 3-task rounds. The number of rounds can be calculated with the formula `(count + 2) / 3`, which is equivalent to `ceil(count / 3.0)`. We add this number to our total rounds and reset the count for the new task difficulty. We repeat this process until the entire array is traversed.

```java
import java.util.Arrays;

class Solution {
    public int minimumRounds(int[] tasks) {
        if (tasks.length == 0) {
            return 0;
        }
        Arrays.sort(tasks);
        int totalRounds = 0;
        int i = 0;
        while (i < tasks.length) {
            int j = i;
            while (j < tasks.length && tasks[j] == tasks[i]) {
                j++;
            }
            int count = j - i;
            if (count == 1) {
                return -1;
            }
            totalRounds += (count + 2) / 3;
            i = j;
        }
        return totalRounds;
    }
}
```
### Algorithm
1. Sort the input array `tasks`.
2. Initialize `totalRounds = 0`.
3. Initialize a pointer `i = 0` to traverse the array.
4. While `i < tasks.length`:
    a. Initialize a second pointer `j = i`.
    b. While `j < tasks.length` and `tasks[j] == tasks[i]`, increment `j`.
    c. Calculate the count of the current task: `count = j - i`.
    d. If `count == 1`, it's impossible to complete this task, so return -1.
    e. Calculate rounds for this group using the formula: `rounds = (count + 2) / 3`.
    f. Add `rounds` to `totalRounds`.
    g. Move the main pointer to the next new task: `i = j`.
5. Return `totalRounds`.

## Hash Map Frequency Count
This is the optimal approach. It involves a single pass to count the frequency of each task difficulty using a hash map, followed by another pass through the map's entries to calculate the total rounds. This avoids the need for sorting.
**Time:** O(N), where N is the number of tasks. We iterate through the `tasks` array once to build the frequency map (O(N)) and then iterate through the unique tasks in the map (O(U), where U is the number of unique tasks, U <= N). The total time is O(N + U) = O(N). · **Space:** O(U), where U is the number of unique tasks. In the worst case, all tasks are unique, so the space complexity is O(N).
**Pros:** Optimal time complexity of O(N).; The logic is clean and directly addresses the problem structure by grouping tasks first.
**Cons:** Requires extra space for the hash map, which could be up to O(N) in the worst case where all tasks are unique.
### Explanation
The problem can be broken down by task difficulty. The number of rounds for one difficulty level is independent of the others. The total rounds is the sum of rounds for each difficulty. We can efficiently count the occurrences of each task difficulty using a hash map. We iterate through the `tasks` array once, and for each task, we increment its corresponding count in the map. After building the frequency map, we iterate through the counts (the values of the map). For each `count`, if it is 1, it's impossible to complete this task, so we return -1. Otherwise, we need to find the minimum number of rounds. The goal is to express `count` as `2*a + 3*b` such that `a+b` is minimized. This is achieved by maximizing `b`, the number of 3-task rounds. A simple mathematical observation reveals the formula for the minimum rounds. If `count % 3 == 0`, we use `count / 3` rounds. If `count % 3 == 1`, we can use `(count/3 - 1)` rounds of 3 and two rounds of 2. If `count % 3 == 2`, we can use `count/3` rounds of 3 and one round of 2. All these cases can be unified by the formula `(count + 2) / 3` using integer division, which is equivalent to `ceil(count / 3.0)`. We sum up the rounds calculated for each distinct task difficulty to get the final answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int task : tasks) {
            freq.put(task, freq.getOrDefault(task, 0) + 1);
        }

        int totalRounds = 0;
        for (int count : freq.values()) {
            if (count == 1) {
                return -1;
            }
            totalRounds += (count + 2) / 3;
        }
        return totalRounds;
    }
}
```
### Algorithm
1. Create a `HashMap<Integer, Integer>` to store task frequencies.
2. Iterate through the `tasks` array. For each `task`, update its frequency in the map.
3. Initialize `totalRounds = 0`.
4. Iterate through the values (frequencies) of the hash map.
5. For each `count`:
    a. If `count == 1`, return -1.
    b. Add `(count + 2) / 3` to `totalRounds`.
6. Return `totalRounds`.

# Solutions
### Java

```java
class Solution {
public
  int minimumRounds(int[] tasks) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int t : tasks) {
      cnt.merge(t, 1, Integer : : sum);
    }
    int ans = 0;
    for (int v : cnt.values()) {
      if (v == 1) {
        return -1;
      }
      ans += v / 3 + (v % 3 == 0 ? 0 : 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumRounds(vector<int> &tasks) {
    unordered_map<int, int> cnt;
    for (auto &t : tasks) {
      ++cnt[t];
    }
    int ans = 0;
    for (auto &[_, v] : cnt) {
      if (v == 1) {
        return -1;
      }
      ans += v / 3 + (v % 3 != 0);
    }
    return ans;
  }
};

```

### Python

```python
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

```