#K90592. Maximize Seated Customers
Maximize Seated Customers
Maximize Seated Customers
You are given several test cases. In each test case, there are n tables with given seating capacities and m groups of customers with different group sizes. Each group must be seated at the smallest available table that has a capacity greater than or equal to the size of the group. Once a table is used, it cannot be used again.
Formally, given a table capacity array \(T = \{t_1, t_2, \dots, t_n\}\) and a group sizes array \(G = \{g_1, g_2, \dots, g_m\}\), you should seat the groups by assigning each group \(g\) to the smallest table \(t\) such that \(t \geq g\). The goal is to maximize the sum of the group sizes that are seated.
This problem can be solved using a greedy strategy where both the tables and the groups are sorted. Then, you iterate through the groups and assign each group to the first table that fits.
inputFormat
The first line contains an integer \(T\), the number of test cases. Each test case is described as follows:
- The first line contains two integers \(n\) and \(m\): the number of tables and the number of groups respectively.
- The second line contains \(n\) integers representing the seating capacities of the tables.
- The third line contains \(m\) integers representing the sizes of the groups.
All input is provided via stdin.
outputFormat
For each test case, output a single line containing the total number of customers successfully seated, via stdout.
## sample2
3 4
4 8 2
5 3 2 4
2 3
10 5
6 6 6
9
6
</p>