DEV Community

Cover image for 2244. Minimum Rounds to Complete All Tasks
Rohith V
Rohith V

Posted on

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (3)

Collapse
 
groegvolokin profile image
groegvolokin • Edited

Good solution Rohith! Here is mine. First I sort the array and then I keep track how many are with the same size and then do the math.

public class Solution {

    public int minimumRounds(int[] tasks) {
        if (tasks.length == 0) return 0;
        if (tasks.length == 1) return -1;
        Arrays.sort(tasks);
        int currentTaskCount = 1;
        int numberOfRounds = 0;

        for (int i = 1; i < tasks.length; i++) {
            if (tasks[i] == tasks[i - 1]) {
                currentTaskCount++;
            } else {
                if (currentTaskCount < 2) return -1;
                numberOfRounds += (currentTaskCount + 2) / 3;
                currentTaskCount = 1;
            }
        }
        if (currentTaskCount < 2) return -1;
        numberOfRounds += (currentTaskCount + 2) / 3;
        return numberOfRounds;
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rohithv07 profile image
Rohith V • Edited

Nice to know about a different approach. Will the TC will be O(nlogn) due to sorting?

Collapse
 
groegvolokin profile image
groegvolokin • Edited

Yes, the sorting will take O(nlogn) the rest would be O(n). On this small inputs like this the performance would be hardly noticeable. However this is what I got from LeetCode using my solution.

Image description