Split Stay Algorithm

Split Stay Booking Algorithm

You're building Airbnb's innovative Split Stay feature, which allows guests to book their trip across multiple listings when a single property isn't available for their entire stay.

Given:

• A list of available listings, each with availability windows and nightly rates
• A guest's desired check-in date, check-out date, and party size

Write an algorithm that finds the optimal combination of listings to cover the guest's entire stay while minimizing total cost.

Rules:

1. The guest's stay must be fully covered with no gaps
2. Each listing can only be used once per booking
3. Listings must accommodate the party size
4. Transitions between listings can only happen at midnight (no same-day switches)
5. If multiple optimal solutions exist, prefer fewer transitions (fewer listings)

Input Format:

• check_in: Start date (string, "YYYY-MM-DD")
• check_out: End date (string, "YYYY-MM-DD")
• party_size: Number of guests (integer)
• listings: Array of listing objects with:
  • id: Listing identifier (string)
  • capacity: Max guests (integer)
  • available_from: Start of availability (string, "YYYY-MM-DD")
  • available_to: End of availability (string, "YYYY-MM-DD")
  • nightly_rate: Cost per night (float)

Output Format:

Return an array of booking segments, each containing:

• listing_id: The listing to book
• start_date: Check-in for this segment
• end_date: Check-out for this segment
• cost: Total cost for this segment

Return an empty array if no valid split-stay combination exists.