Split-Stay Pair Finder API

Context

You are designing part of Airbnb's "Split Stay" search feature. A guest requests a date range (check-in to check-out). You are given a set of candidate listings and their per-day availability. A split stay allows the guest to stay in at most two listings during the trip.

Task

Design and implement an API endpoint that, given:

• a requested date range [check_in, check_out), and
• a set of candidate listings with their available nights in that range,

returns every pair of listings whose combined availability can cover the full stay. Assume nights are the days from check_in (inclusive) to check_out (exclusive).

Requirements

1. API design

• Define method, path, request, and response schema.
• Dates must be ISO-8601, time zone-aware (assume UTC for simplicity).

2. Matching semantics

• Default: one-switch feasibility (guest moves at most once). That is, there exists a split point k such that the first k nights are available in listing A and the remaining nights are available in listing B.
• Optional: union coverage mode (feature flag) where the union of A and B availability covers all requested nights (may require multiple moves; mainly for diagnostics/testing).

3. Functional behavior

• Do not pair a listing with itself.
• Deduplicate symmetric pairs (A,B) and (B,A); return a canonical ordering but include a recommended split plan.
• Include at least one valid split plan (dates/nights on each listing) for one-switch mode.

4. Performance and constraints (make reasonable assumptions)

• Number of candidate listings M up to 5,000 per request.
• Stay length N up to 30 nights.
• Return results with pagination/limits.

5. Edge cases

• No qualifying pairs → return empty list with 200.
• Single listing fully covering the range is not considered (this endpoint focuses on pairs), but you may return a hint if desired.
• Handle partial/blocked days by modeling availability at the night granularity.

6. Provide a brief explanation of your algorithm, complexity, and any data structures used.