DEV Community

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

Posted on

1

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.

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

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

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More