Fill a layover with the fewest bookings

This is coin change in a travel costume. The layover length is the target amount, each experience's duration is a coin, and an experience can be booked any number of times. We want the fewest bookings that add up to exactly the layover, and usually the itinerary itself, not just the count.

Greedy is wrong, and saying why is the first checkpoint. "Always take the longest experience that still fits" fails on durations [1, 3, 5, 6] with an 8-hour layover: greedy books 6 + 1 + 1 (3 bookings), but 5 + 3 needs only 2. Greedy also fails outright on [5, 3] with 9 hours: it books 5, has 4 left, and gets stuck, while 3 + 3 + 3 works.

Brute force. Recursively try every experience as the next booking and recurse on the remaining hours, keeping the minimum. That is exponential, but it shows the recurrence:

best(h) = 1 + min(best(h - d) for each duration d <= h), with best(0) = 0.

The same h is reached through many different orderings, so memoizing it collapses the work to one value per hour.

Optimal: bottom-up DP over hours.

• best[h] is the fewest bookings that fill exactly h hours, or infinity if h cannot be filled.
• choice[h] is the experience booked last in that best plan.
• Fill h = 1 .. total in order. For each experience with duration d <= h, try best[h - d] + 1.
• To rebuild the itinerary, start at total, take choice[h], subtract its duration, and repeat until h is 0.

Ties are broken by the first experience in input order, which keeps the output deterministic.

Why it is correct. Any optimal plan for h has some last booking d, and the rest of that plan must be an optimal plan for h - d (otherwise swap in a shorter one). Order does not matter because bookings are a multiset, so considering "the last booking" over all d covers every plan.

Alternative: BFS. Treat each hour count as a node and each booking as an edge of weight 1. The fewest bookings is the shortest path from 0 to total. BFS can stop early as soon as it reaches total, which helps when the answer is small. The worst case matches the DP.

Edge cases to state up front.

• total == 0: zero bookings, empty itinerary.
• No combination fits: return -1 (or None for the itinerary).
• Durations that are 0 or negative are invalid input. Raise, or drop them, and say which.
• Durations longer than the layover simply never get used.
• Duplicate durations are harmless.

Invariants.

• best[0] == 0, and best[h] is final once the loop moves past h.
• If best[h] is finite, following choice from h reaches exactly 0 in best[h] steps.

from collections import deque
from dataclasses import dataclass
from typing import List, Optional, Sequence


@dataclass(frozen=True)
class Experience:
    name: str
    hours: int


def min_bookings(durations: Sequence[int], total_hours: int) -> int:
    """Fewest bookings summing to exactly total_hours, or -1 if impossible."""
    if total_hours < 0:
        raise ValueError("total_hours must be non-negative")
    if any(d <= 0 for d in durations):
        raise ValueError("durations must be positive")
    inf = total_hours + 1
    best = [0] + [inf] * total_hours
    for h in range(1, total_hours + 1):
        for d in durations:
            if d <= h and best[h - d] + 1 < best[h]:
                best[h] = best[h - d] + 1
    return best[total_hours] if best[total_hours] < inf else -1


def plan_layover(experiences: Sequence[Experience], total_hours: int) -> Optional[List[Experience]]:
    """Return a shortest itinerary that fills the layover exactly, or None."""
    if total_hours < 0:
        raise ValueError("total_hours must be non-negative")
    if any(e.hours <= 0 for e in experiences):
        raise ValueError("experience durations must be positive")

    inf = total_hours + 1
    best = [0] + [inf] * total_hours
    choice: List[int] = [-1] * (total_hours + 1)  # index of the last experience booked
    for h in range(1, total_hours + 1):
        for i, exp in enumerate(experiences):
            d = exp.hours
            if d <= h and best[h - d] + 1 < best[h]:
                best[h] = best[h - d] + 1
                choice[h] = i

    if best[total_hours] >= inf:
        return None
    plan: List[Experience] = []
    h = total_hours
    while h > 0:
        exp = experiences[choice[h]]
        plan.append(exp)
        h -= exp.hours
    return plan


def min_bookings_bfs(durations: Sequence[int], total_hours: int) -> int:
    """Same answer via BFS over hours filled; stops as soon as the target is hit."""
    if total_hours == 0:
        return 0
    seen = [False] * (total_hours + 1)
    seen[0] = True
    queue = deque([0])
    steps = 0
    while queue:
        steps += 1
        for _ in range(len(queue)):
            filled = queue.popleft()
            for d in durations:
                nxt = filled + d
                if nxt == total_hours:
                    return steps
                if nxt < total_hours and not seen[nxt]:
                    seen[nxt] = True
                    queue.append(nxt)
    return -1


if __name__ == "__main__":
    tour, hike, spa, class_ = (Experience("food tour", 6), Experience("hike", 5),
                               Experience("spa", 3), Experience("cooking class", 1))
    plan = plan_layover([tour, hike, spa, class_], 8)
    assert plan is not None and sorted(e.hours for e in plan) == [3, 5]
    assert min_bookings([1, 3, 5, 6], 8) == 2
    assert min_bookings([5, 3], 9) == 3
    assert min_bookings([4, 6], 7) == -1
    assert plan_layover([Experience("a", 4), Experience("b", 6)], 7) is None
    assert min_bookings([2], 0) == 0 and plan_layover([Experience("a", 2)], 0) == []
    assert min_bookings([2, 7], 11) == 3  # 7 + 2 + 2
    for ds in ([1, 3, 5, 6], [5, 3], [4, 6], [2, 7], [7, 11, 13]):
        for t in range(0, 60):
            assert min_bookings(ds, t) == min_bookings_bfs(ds, t), (ds, t)
    print("ok")

Let T be the layover in hours and n the number of experiences.

• min_bookings / plan_layover: O(T · n) time, O(T) space for best and choice.
• Rebuilding the itinerary: O(answer) ≤ O(T / min duration).
• min_bookings_bfs: O(T · n) time and O(T) space in the worst case, often far less when the answer is small because it stops at the first level that reaches T.

The DP is pseudo-polynomial: it scales with the numeric value of T, not with the size of the input. That is fine for hours in a layover; it matters in follow-up 2.

• Durations [1, 3, 5, 6], layover 8 → 2 bookings (5 + 3). Greedy would give 3.
• Durations [5, 3], layover 9 → 3 bookings (3 + 3 + 3). Greedy gets stuck.
• Durations [4, 6], layover 7 → -1 / None (every sum is even).
• Durations [2, 7], layover 11 → 3 (7 + 2 + 2).
• Layover 0 → 0 bookings, empty itinerary.
• Durations [10], layover 4 → -1 (every experience is longer than the layover).
• Durations [3, 3, 3] (duplicates), layover 6 → 2.
• Durations [1], layover 1000 → 1000 (worst-case itinerary length).
• Duration 0 or negative in the input → ValueError.
• DP and BFS agree on every layover from 0 to 59 for several duration sets (the self-check in the code).

1. Each experience can be booked at most k times (or once). This becomes bounded knapsack. For "at most once", iterate experiences in the outer loop and hours from high to low, as in 0/1 knapsack. For a count k, either expand into k copies or use binary splitting (copies of size 1, 2, 4, ...) to keep it O(T · Σ log k).
2. Durations are fractional (for example 1.5 hours) or the layover is huge. Scale everything by the least common unit (half hours, 15-minute slots) to stay in integers; never DP on floats. If T is enormous but durations are small, divide out the gcd first, and note that with BFS the search can stop early. Checking T % gcd(durations) == 0 rejects impossible inputs in O(n).
3. Count the number of distinct itineraries. Same DP shape with sums instead of mins. If order does not matter (combinations), put experiences in the outer loop so each multiset is counted once; if order matters (schedules), put hours in the outer loop.
4. Each experience has a price; fill the layover with the fewest bookings, then the lowest cost. Store a tuple (bookings, cost) per hour and compare lexicographically, or minimize cost only if the interviewer changes the objective. The recurrence and reconstruction are unchanged.
5. Allow some slack: the layover must be filled to within s hours, leaving buffer for security. Run the same DP once and take the best best[h] over h in [T - s, T], preferring larger h on ties. One pass covers every target at once.

Mid-level (L4)

• Recognizes this as coin change and explains with a counterexample why greedy fails.
• Writes a correct bottom-up or memoized DP that returns the minimum count, and -1 when impossible.
• Handles a 0-hour layover and experiences longer than the layover.

Senior (L5)

• Returns the actual itinerary through a parent/choice array, not just the count.
• States O(T · n) time and calls out that it is pseudo-polynomial.
• Validates input (non-positive durations) and tests impossible and greedy-trap cases without prompting.
• Handles the bounded "book each at most once" follow-up by changing loop order, and explains why the order matters.

Staff (L6+)

• Compares DP and BFS and says when early exit or gcd pruning wins.
• Handles fractional durations by choosing an integer time unit and explains the cost in table size.
• Extends cleanly to multi-objective choices (bookings then price) and slack windows without rewriting the core loop.
• Talks about the product: real itineraries need travel time between experiences and opening hours, which turns this into scheduling, and says where the simple model stops being enough.