Find a split-stay booking across listings
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are implementing a simplified **split-stay** search.
You are given:
- A desired trip interval **[start, end)**, where dates are represented as integers (e.g., days). The guest stays nights `start, start+1, ..., end-1`.
- `n` listings. For each listing `i`, you are given a set of **available** (bookable) date intervals `avail[i]`, each as **[li, ri)**. Intervals within a listing are non-overlapping and sorted.
A trip is feasible if it can be covered by:
1. **One listing** that is available for the entire interval **[start, end)**, OR
2. **Exactly two listings** `(A, B)` with a single switch day `mid` such that:
- Listing `A` covers **[start, mid)**
- Listing `B` covers **[mid, end)**
- `start < mid < end` (both stays are non-empty)
- There are **no gaps** and no overlap requirements beyond continuous coverage.
### Task
Return whether the trip is feasible. If feasible, return **one valid plan**:
- Either `(A)` for a single-listing stay, or
- `(A, B, mid)` for a split stay.
### Constraints (you may assume)
- `1 ≤ n ≤ 2e5`
- Total number of availability intervals across all listings ≤ `2e5`
- Dates fit in 32-bit signed integers.
### Notes
- Listings are identified by integer IDs `0..n-1`.
- Availability intervals are inclusive of `li` and exclusive of `ri`.
Quick Answer: This question evaluates understanding of interval coverage and algorithmic problem solving, specifically reasoning about continuous date ranges, split-interval feasibility, and efficient handling of multiple sorted availability intervals.
You are implementing a simplified split-stay search.
You are given a desired trip interval [start, end), where dates are integers. The guest stays nights start, start+1, ..., end-1.
There are n listings, identified by IDs 0..n-1. For each listing i, avail[i] is a sorted list of non-overlapping availability intervals (li, ri), meaning the listing is bookable on [li, ri).
A trip is feasible if it can be covered by either:
1. One listing that covers the entire interval [start, end), or
2. Two distinct listings A and B with exactly one switch day mid such that:
- start < mid < end
- listing A covers [start, mid)
- listing B covers [mid, end)
- there are no gaps in coverage
Adjacent intervals inside the same listing, such as (3, 5) and (5, 7), should be treated as continuous availability.
Return a pair (feasible, plan):
- (True, (A,)) if one listing covers the entire trip
- (True, (A, B, mid)) if a valid split-stay plan exists
- (False, None) if no valid plan exists
If multiple valid plans exist, returning any one of them is acceptable.
Constraints
- 1 <= len(avail) <= 2 * 10^5