Split Stay: Two-Listing Date Coverage

Question

## Problem

Airbnb supports “split stays,” where a guest can book the first part of a trip at one listing and the second part of the trip at another listing.

You are given a set of Airbnb listings. Each listing has a list of available days represented as integers.

Given a requested date range `[startDate, endDate]`, return every pair of two distinct listings that can cover the entire range as a valid split stay.

A valid split stay means:

- The first listing covers a contiguous prefix of the date range.
- The second listing covers the remaining contiguous suffix.
- There is exactly one switch point between the two listings.
- The two stays do not overlap.
- Both parts must be fully covered by the corresponding listing’s availability.

More formally, for some split day `k` where `startDate <= k < endDate`:

- Listing A covers every day in `[startDate, k]`
- Listing B covers every day in `[k + 1, endDate]`

The pair `(A, B)` is valid if such a split exists.

## Function Signature

```python
def find_split_stays(
    listings: dict[str, list[int]],
    start_date: int,
    end_date: int
) -> list[tuple[str, str]]:
    pass
```

## Input

```python
listings = {
    "A": [1, 2, 3, 6,

Accepted Answer

A detailed reference solution is available to Crack ML Interview members.