Closest Festival Menu
Preview mode. Log in to edit, run, submit, and save progress.
Medium
Closest Festival Menu
A festival menu has several shelves. You must choose exactly one item price from each shelf. The total price of the chosen items should be as close as possible to a given budget. Return the minimum absolute difference between the final total price and the budget.
Examples
Example 1
Input:
menus = [[4,8,12],[3,10,15],[6,7,20]], budget = 23
Output:
1
Explanation: One closest bundle is 8 + 10 + 6 = 24, giving a gap of 1.
Approach hint
Keep track of which totals are reachable after each shelf.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
solution.cpp