2244. Minimum Rounds to Complete All Tasks

Question

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

Intuition

In each round, we can complete either 2 or 3 tasks with the same difficulty. We actually need to find the minimum number of rounds, so it's ideal to complete 3 tasks because it will reduce the number of rounds.
Example: say we have 6 x tasks. To get the minimum, it is always better to complete 3, 3 tasks than 2, 2, 2 tasks.

Approach

So first of all we actually need to consider the count and a hashmap can be best used for this scenario. After taking the count and storing it in the hashmap, iterate through the hashmap and check whether the count is < 2. This is our base condition and we can return -1 right away.
Otherwise, just try to find how many 3 jobs + 3 jobs + …. + 2 jobs count.
This can be achieved by (currentCount + 2) / 3 and adding this result to the minimum round.

Complexity

• Time complexity: O(n) + O(n) because we are traversing through the array first and then through the hashmap which can have approx. n elements in the worst case.
• Space complexity: We use an extra hashmap to store the count of each task; it can be n in the worst case. So space complexity will be O(n).

Code

class Solution {
    public int minimumRounds(int[] tasks) {
        int length = tasks.length;
        if (tasks == null || length == 0) {
            return 0;
        }
        int roundCount = 0;
        Map<Integer, Integer> taskCount = new HashMap<>();
        for (int task : tasks) {
            taskCount.put(task, taskCount.getOrDefault(task, 0) + 1);
        }
        for (Integer taskKey : taskCount.keySet()) {
            int currentKeyCount = taskCount.get(taskKey);
            if (currentKeyCount < 2) {
                return -1;
            }
            roundCount += (currentKeyCount + 2) / 3;
        }
        return roundCount;
    }
}

Please feel free to discuss about any different idea or different approach.