Fill a layover with the fewest bookings

You land with a long layover and want to spend all of it on bookable local experiences. Each experience has a fixed whole-number duration in hours, and you may book the same experience as many times as you like (back to back).

Given the list of experiences and the layover length total_hours, find the fewest bookings whose durations add up to exactly total_hours.

Implement:

def min_bookings(durations: list[int], total_hours: int) -> int: ...
def plan_layover(experiences: list[Experience], total_hours: int) -> list[Experience] | None: ...

• min_bookings returns the minimum number of bookings, or -1 if the layover cannot be filled exactly.
• plan_layover returns one itinerary that achieves that minimum (any order), or None if it is impossible. Experience has a name and an hours field.

Constraints

• 0 <= total_hours <= 10^4
• 1 <= len(durations) <= 100, each duration is a positive integer.
• A 0-hour layover needs 0 bookings.

Example 1

Experiences: kayak trip (5h), museum visit (2h), city walk (7h). Layover: 11 hours.

Answer: 3 bookings, for example city walk + museum visit + museum visit (7 + 2 + 2). Two bookings cannot reach 11.

Example 2

Durations [4, 6], layover 9 hours. Every combination sums to an even number, so the answer is -1.

Be ready to explain why always picking the longest experience that still fits does not work.