Group Accommodation: Assign Guests to Rooms Minimizing Wasted Capacity

Question

## Problem

You have a list of hotel rooms with capacities and a list of guest groups with sizes. Assign each group to exactly one room such that the room capacity is >= group size and the total wasted capacity (sum of `capacity - group_size` across all assignments) is minimized. Each room can hold at most one group.

Return the minimum total wasted capacity, or -1 if a valid assignment is impossible.

```python
def min_wasted_capacity(rooms: list[int], groups: list[int]) -> int:
    pass
```

**Example:**
```
Input:  rooms = [3, 5, 8], groups = [2, 4]
Assignments:
  Group 2 -> Room 3 (waste=1), Group 4 -> Room 5 (waste=1): total=2
  Group 2 -> Room 5 (waste=3), Group 4 -> Room 8 (waste=4): total=7
Output: 2
```

## Approach

Sort both arrays. Use a greedy approach: for each group (ascending), assign the smallest room that fits. This is a classic greedy / two-pointer problem.

## Follow-ups

1. What is the time complexity after sorting? Prove the greedy is optimal.
2. What if each room has a price and you want to minimize total cost (not waste)?
3. What if groups have preferences (list of acceptable room IDs)? Does greedy still work?
4. How would you model this as a bipartite matching problem?

Group Accommodation: Assign Guests to Rooms Minimizing Wasted Capacity

Question Details

Full Details

Topics

More from Airbnb