Katkat
Back

Minimize exact layover bookings

AirbnbMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use dynamic programming to determine if a specific target sum can be achieved using a subset of given item values and how to find the minimum subset size that hits that target.

Problem Statement

Airbnb's reservation system is auditing a series of guest stays. Each booking in a list has a specific duration in days. You are given a list of integers durations representing these bookings and a target integer total_days representing a planned long-term trip duration.

Your task is to find the minimum number of bookings required such that the sum of their durations equals total_days exactly. If it is impossible to reach the sum exactly, return -1.

Function Signature

def min_bookings_for_target(durations: List[int], total_days: int) -> int:

Examples

Example 1: Input: durations = [2, 3, 5, 7], total_days = 10 Output: 2 Explanation: 3 + 7 = 10 (2 bookings). 2 + 3 + 5 = 10 (3 bookings). The minimum is 2.

Example 2: Input: durations = [1, 1, 1], total_days = 4 Output: -1 Explanation: It is impossible to sum to 4 with the available durations.

Constraints

  • 1 <= len(durations) <= 1000
  • 1 <= durations[i] <= 1000
  • 1 <= total_days <= 5000

Edge Cases

  • If total_days is 0, the answer should be 0.
  • If no combination reaches the sum, return -1.

Hints

Hint 1

Consider this a variation of the classic knapsack or change-making problem where you want to minimize the number of items used.

Hint 2

Define a DP array where `dp[i]` stores the minimum number of bookings needed to achieve a sum of exactly `i`.

Hint 3

Initialize the DP array with infinity, set `dp[0] = 0`, and iterate through each duration to update the minimum counts for all possible sums.

Follow-up questions

  • How would your approach change if you were allowed to use each booking duration an unlimited number of times?
  • What is the time and space complexity of your solution, and can you optimize the space complexity?
  • If the durations were very large and the target was in the millions, how would you approach the problem if a greedy strategy is no longer optimal?