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:
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.
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.
Approach: The first approach that came to my mind is that it is similar to Coin Change problem. Basically we use a map to count the frequency of each task difficulty. Now for each frequency, the frequency becomes the value and the available coins are of value 2 and 3. We can get the minimum number of coins to make this value(frequency). We can then sum up this for all tasks and this sum will be our answer. We can optimize it further a bit, if we fill our DP table for the maximum frequency then we don't have to repeat our calculation for other frequencies as these are already filled.
Can we do better? The above solution is taking O(n) time and space (max frequency can't be more than number of tasks). The above solution is doing 3 passes; one for frequency calculation, second for filling the DP table and third one is for final calculation of rounds. It is also taking 2 * n space; Map and DP table. Let's try to do reduce the number of passes and space.
If you remember except 1 any natural number can be written in the form of 3x + 2y. In order to minimize the (x + y) which is our answer (number of rounds), we need to maximize x. With this intuition/greed, Let's see how we can solve this question.
Given that we want maximize x, we can say the number could be of 3 types:
- 3 * x (multiple of 3)
- 3 * x + 1 (Remainder 1)
- 3 * x + 2 (Remainder 2)
In the first case answer is straight forward i.e. x but what to do in the next two cases. First let's take the easy case which is the third case; 3 * x + 2, we can see that here y is 1 (3 * x + 2 * y), so the answer will be x + 1.
Now let's look at remaining case which is 3 * x + 1. We need it in the form of 3 * x + 2 * y so we can do the following:
3 * x + 1
= > 3 * ( x - 1 + 1) + 1;
=> 3 * x - 3 + 3 + 1
=> 3 * x - 3 + 4
=> 3 * (x - 1) + 4
=> 3 * (x - 1) + 2 * 2
=> 3 * z + 2 * 2 where z = x - 1
so here y is 2 and x is z. The sum of x + y = z + 2 = (x - 1) + 2 = x + 1.
So we can see that in both cases 2 and 3 the answer is x + 1. Where x is N / 3.
That's all about the approach!
Implementation in C#:
Approach 1: DP:
public int MinimumRounds(int[] tasks)
{
Dictionary<int, int> taskFreqMap = new Dictionary<int, int>();
int maxFreq = 0;
foreach (int task in tasks)
{
if (!taskFreqMap.ContainsKey(task))
{
taskFreqMap[task] = 0;
}
++taskFreqMap[task];
if (maxFreq < taskFreqMap[task])
{
maxFreq = taskFreqMap[task];
}
}
if (maxFreq < 2)
{
return -1;
}
int rounds = 0;
int[] table = new int[maxFreq + 1];
table[2] = 1;
if (maxFreq >= 3)
{
table[3] = 1;
}
this.DistributeTasks(maxFreq, table);
foreach (var taskItem in taskFreqMap)
{
int currFreq = taskItem.Value;
if (table[currFreq] == 0)
{
return -1;
}
rounds += table[currFreq];
}
return rounds;
}
private void DistributeTasks(int value, int[] table)
{
if (value < 2)
{
return;
}
for (int i = 4; i <= value; ++i)
{
if (table[i - 2] == 0 && table[i - 3] == 0)
{
table[i] = 0;
continue;
}
if (table[i - 2] == 0)
{
table[i] = table[i - 3] + 1;
}
else if (table[i - 3] == 0)
{
table[i] = table[i - 2] + 1;
}
else
{
table[i] = Math.Min(table[i - 2], table[i - 3]) + 1;
}
}
}
Approach 2: Math:
public int MinimumRounds(int[] tasks)
{
Dictionary<int, int> taskFreqMap = new Dictionary<int, int>();
foreach (int task in tasks)
{
if (!taskFreqMap.ContainsKey(task))
{
taskFreqMap[task] = 0;
}
++taskFreqMap[task];
}
int rounds = 0;
foreach (var taskItem in taskFreqMap)
{
int currFreq = taskItem.Value;
if (currFreq < 2)
{
return -1;
}
if (currFreq % 3 == 0)
{
rounds += (currFreq / 3);
}
else
{
rounds += (currFreq / 3 + 1);
}
}
return rounds;
}
Complexity: O(n) in both approaches.
