You're stuck in a city for exactly total_hours hours between flights and want to fill every hour with bookable experiences (a food tour, a museum visit, ...). Each experience has a unique name and a fixed length in whole hours, and any experience can be booked repeatedly. The bookings must add up to exactly total_hours, and you want as few bookings as possible.
You must return the actual plan, not just its size.
def plan_layover(experiences: list[tuple[str, int]], total_hours: int) -> list[str] | None
experiencesis a list of(name, hours)with distinct names andhours >= 1. Different experiences may have the same length.- Return the plan as a list of names sorted alphabetically (a name appears once per booking).
- If several plans use the fewest bookings, return the one whose sorted list is lexicographically smallest (compare the lists element by element, like Python's
<on lists). total_hours == 0gives[]. If the time can't be filled exactly, returnNone.
exps = [("kayak", 3), ("market", 2), ("tour", 5), ("zoo", 3)]
plan_layover(exps, 11) # ["kayak", "kayak", "tour"]
# 3 bookings is the minimum: {3, 3, 5}. kayak/zoo are both 3 hours;
# ["kayak", "kayak", "tour"] < ["kayak", "tour", "zoo"] < ["tour", "zoo", "zoo"]
plan_layover(exps, 1) # None
plan_layover([("walk", 2)], 0) # []
Constraints: up to 100 experiences, total_hours <= 10,000. Plain recursion over choices is exponential; aim for O(len(experiences) * total_hours).
Show hint
this is the fewest-coins problem with a twist. First compute dp[t] = the fewest bookings that fill exactly t hours. Then build the answer from the front: with t hours left, pick the alphabetically smallest name whose length h has dp[t - h] == dp[t] - 1, and repeat. The names you pick this way come out already sorted: think about why a smaller name can't show up later.