Match Each Guest With a Snack Big Enough
Solve this ProblemA host has several guests and several snacks. A guest is satisfied by any single snack whose size is at least their appetite. Each guest can be given at most one snack, and each snack can go to at most one guest. Find the largest number of guests that can be satisfied.
Trying every possible hand-out works, but the number of possibilities explodes. A greedy rule cuts it down: sort both lists, and always serve the least hungry remaining guest with the smallest snack that can do the job.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ appetite.length ≤ 8 and 1 ≤ snacks.length ≤ 8 - ◆
1 ≤ appetite[i], snacks[j] ≤ 50 - ◆
A guest with appetite a is satisfied by any single snack of size ≥ a; each guest gets at most one snack and each snack goes to at most one guest - ◆
Return the largest number of guests that can be satisfied
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Way to Hand Out the Snacks
BruteDecide guest by guest. For the current guest, either leave them unsatisfied and move on, or give them any unused snack that is big enough and move on. Recurse through all of these choices and keep the best count. This is guaranteed correct because it literally tries every possible assignment — but the number of assignments explodes as guests and snacks are added, which is why the input sizes here are tiny.
O((m + 1)ⁿ)O(n + m)1class Solution {
2 public int maxHappyGuests(int[] appetite, int[] snacks) {
3 return explore(appetite, snacks, new boolean[snacks.length], 0);
4 }
5
6 private int explore(int[] appetite, int[] snacks, boolean[] used, int guest) {
7 if (guest == appetite.length) return 0;
8 int best = explore(appetite, snacks, used, guest + 1);
9 for (int s = 0; s < snacks.length; s++) {
10 if (!used[s] && snacks[s] >= appetite[guest]) {
11 used[s] = true;
12 best = Math.max(best, 1 + explore(appetite, snacks, used, guest + 1));
13 used[s] = false;
14 }
15 }
16 return best;
17 }
18}Optimal — Sort Both Lists and Sweep With One Pointer
OptimalSort the appetites and the snack sizes. The hungriest guests are the hardest to satisfy, so serve the least hungry guest first, and serve them with the smallest snack that works — never waste a big snack on a small appetite. Walk through the snacks from smallest to largest while keeping a pointer at the least hungry guest still unserved: if the snack is big enough for that guest, serve them and advance the pointer; if not, the snack is too small for everyone remaining (they are all at least as hungry), so discard it. The pointer's final position is the number of satisfied guests.
O(n log n + m log m)O(n + m)1class Solution {
2 public int maxHappyGuests(int[] appetite, int[] snacks) {
3 int[] guests = appetite.clone();
4 int[] sizes = snacks.clone();
5 Arrays.sort(guests);
6 Arrays.sort(sizes);
7 int guest = 0;
8 for (int size : sizes) {
9 if (guest < guests.length && size >= guests[guest]) guest++;
10 }
11 return guest;
12 }
13}