Given an integer batchSize and an array groups where groups[i] is the number of people in the i-th group waiting for donuts, you are to distribute donuts in batches of size batchSize. Each batch is made fresh and can serve up to batchSize people. Groups are served in order, and you can only start a new batch if the previous one is finished.
A group is considered "happy" if the first person in the group gets a fresh donut (i.e., the batch is empty when they arrive). Your goal is to reorder the groups (in any order) to maximize the number of happy groups.
Constraints:
batchSize ≤ 9groups.length ≤ 30groups[i] ≤ 109At first glance, the problem seems to require checking all permutations of the group order to maximize the number of happy groups. However, with up to 30 groups, trying all permutations is infeasible (30! is enormous).
The key insight is that a group is happy if it arrives when the batch is empty, i.e., the current donut count modulo batchSize is zero. The order of groups can be rearranged, so we can optimize the sequence.
Instead of thinking about the actual values in groups, we can focus on the remainders when each group's size is divided by batchSize. This is because only the remainder affects the batch status.
The challenge is to efficiently explore possible groupings and orderings without brute-forcing all permutations, possibly using memoization or dynamic programming to avoid redundant calculations.
To solve this problem efficiently, we use a dynamic programming approach with memoization. Here’s the step-by-step breakdown:
group % batchSize. This tells us how much of the current batch they will "use up" and is all that matters for subsequent calculations.
batchSize - 1), count how many groups have that remainder.
curr value (how many donuts are left in the current batch).
curr == 0 (batch is empty), the group is happy. Recurse and take the maximum.
batchSize is at most 9 and there are at most 30 groups), we can cache results for each unique state to avoid recomputation.
This approach is efficient and leverages the small size of batchSize and the fact that only the counts of each remainder matter, not the specific group sizes.
Suppose batchSize = 3 and groups = [1,2,3,4,5,6].
The DP ensures we consider all possible valid orders and pick the one that maximizes happy groups.
Brute-force Approach: Trying all permutations is O(n!), which is infeasible for n up to 30.
Optimized (DP with Memoization):
batchSize options, and memoize results. The total number of states is bounded by (number of ways to distribute 30 indistinguishable balls into (batchSize-1) bins), which is combinatorial but tractable for small batchSize.
The core insight is reducing the problem to remainders modulo batchSize and using dynamic programming with memoization to efficiently explore all possible groupings. By focusing on remainder counts rather than actual group sizes, and leveraging the small batchSize, we avoid brute-force and find the optimal solution efficiently. The approach is both elegant and practical, making use of combinatorial state compression and recursive DP.
from functools import lru_cache
from collections import Counter
class Solution:
def maxHappyGroups(self, batchSize: int, groups: list[int]) -> int:
rems = [g % batchSize for g in groups]
cnt = [0] * batchSize
for r in rems:
cnt[r] += 1
res = cnt[0]
@lru_cache(maxsize=None)
def dfs(state, curr):
ans = 0
for i in range(1, batchSize):
if state[i]:
new_state = list(state)
new_state[i] -= 1
# If curr == 0, this group is happy
add = 1 if curr == 0 else 0
nxt = (curr + i) % batchSize
ans = max(ans, dfs(tuple(new_state), nxt) + add)
return ans
# Start DFS, state is the tuple of counts (cnt[1], ..., cnt[batchSize-1])
return res + dfs(tuple(cnt), 0)
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int batchSize;
unordered_map<string, int> memo;
int dfs(vector<int>& state, int curr) {
string key;
for (int i = 1; i < batchSize; ++i) {
key += to_string(state[i]) + ",";
}
key += to_string(curr);
if (memo.count(key)) return memo[key];
int ans = 0;
for (int i = 1; i < batchSize; ++i) {
if (state[i]) {
state[i]--;
int add = (curr == 0) ? 1 : 0;
int nxt = (curr + i) % batchSize;
ans = max(ans, dfs(state, nxt) + add);
state[i]++;
}
}
memo[key] = ans;
return ans;
}
int maxHappyGroups(int batchSize_, vector<int>& groups) {
batchSize = batchSize_;
vector<int> cnt(batchSize, 0);
for (int g : groups) cnt[g % batchSize]++;
int res = cnt[0];
return res + dfs(cnt, 0);
}
};
import java.util.*;
class Solution {
int batchSize;
Map<String, Integer> memo = new HashMap<>();
public int maxHappyGroups(int batchSize, int[] groups) {
this.batchSize = batchSize;
int[] cnt = new int[batchSize];
for (int g : groups) cnt[g % batchSize]++;
int res = cnt[0];
return res + dfs(cnt, 0);
}
private int dfs(int[] state, int curr) {
StringBuilder sb = new StringBuilder();
for (int i = 1; i < batchSize; ++i) {
sb.append(state[i]).append(",");
}
sb.append(curr);
String key = sb.toString();
if (memo.containsKey(key)) return memo.get(key);
int ans = 0;
for (int i = 1; i < batchSize; ++i) {
if (state[i] > 0) {
state[i]--;
int add = (curr == 0) ? 1 : 0;
int nxt = (curr + i) % batchSize;
ans = Math.max(ans, dfs(state, nxt) + add);
state[i]++;
}
}
memo.put(key, ans);
return ans;
}
}
var maxHappyGroups = function(batchSize, groups) {
let cnt = Array(batchSize).fill(0);
for (let g of groups) cnt[g % batchSize]++;
let res = cnt[0];
let memo = new Map();
function dfs(state, curr) {
let key = state.slice(1).join(',') + ',' + curr;
if (memo.has(key)) return memo.get(key);
let ans = 0;
for (let i = 1; i < batchSize; ++i) {
if (state[i]) {
state[i]--;
let add = (curr === 0) ? 1 : 0;
let nxt = (curr + i) % batchSize;
ans = Math.max(ans, dfs(state, nxt) + add);
state[i]++;
}
}
memo.set(key, ans);
return ans;
}
return res + dfs(cnt, 0);
};