Compute split-stay listing pairs
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given a set of Airbnb listings, each with availability represented as a sorted list of day integers, and a requested inclusive date range [S, E], compute all unordered pairs of listings (X, Y) that can form a split stay covering the entire range. A valid split stay exists if there is an integer T with S ≤ T < E such that listing X has every day from S through T available consecutively and listing Y has every day from T+1 through E available consecutively. Return each pair once (order-insensitive), and specify the algorithm, time/space complexity targets (strive for better than O(L^2 · R)), and edge cases (e.g., missing boundary days, overlapping coverage on both listings, identical availability, or no possible pairs). Example data: A -> [1,2,3,6,7,10,11], B -> [3,4,5,6,8,9,10,13], C -> [7,8,9,10,11]; for [3,11] the valid pair is [B, C].
Quick Answer: This question evaluates the ability to manipulate interval availability data, reason about contiguous date ranges and split boundaries, and design efficient pairing algorithms with attention to time and space complexity.
Given a set of Airbnb listings and the days each one is available, find every pair of listings that can together cover a requested date range as a **split stay** (one listing for the first part of the trip, the other for the rest).
## Input
- `listings`: a map from a **listing ID** (string) to a list of **available day integers**. Each list is sorted in ascending order and contains distinct integers. Days may be negative or positive.
- `S`, `E`: two integers describing the **inclusive requested date range** `[S, E]`, with `S <= E`.
## What to implement
Implement:
```python
def solution(listings, S, E):
```
Return all **unordered pairs of distinct listings** `{X, Y}` that can form a valid split stay covering every day from `S` through `E`.
## When a pair is valid
A pair `{X, Y}` is valid if there exists an integer **split point** `T` with `S <= T < E` such that, assigning one listing to the prefix and the other to the suffix:
- one listing is available on **every** day from `S` through `T` (the consecutive prefix), and
- the other listing is available on **every** day from `T + 1` through `E` (the consecutive suffix).
Additional rules:
- The two roles (prefix vs. suffix) may be assigned in **either order** — the pair counts as valid if *some* split and *some* role assignment works.
- The two listings **may overlap** in coverage, and a single listing may even cover the entire range `[S, E]` by itself. Coverage by one listing alone is fine, but a returned pair must still consist of **two different listing IDs**.
- Because the split point must satisfy `S <= T < E`, when `S == E` no valid split point exists, so the answer is always an empty list.
## Output format
- Return each pair as a 2-element list `[id1, id2]` with the two IDs in **lexicographic (string) order**.
- Return the full list of pairs **sorted lexicographically by pair**.
- Each unordered pair must appear **at most once**.
- If no valid pairs exist, return an **empty list** `[]`.
## Constraints
- `0 <= len(listings) <= 2000`
- `0 <= sum(len(days) for days in listings.values()) <= 200000`
- Each availability list is sorted in ascending order and contains distinct integers.
- Days may be negative or positive integers, and `S <= E`.
Aim for an approach better than checking every pair across every day in the range.
Constraints
- 0 <= len(listings) <= 2000
- 0 <= sum(len(days) for days in listings.values()) <= 200000
- Each availability list is sorted in ascending order and contains distinct integers
- Days may be negative or positive integers, and S <= E
- If S == E, the answer is always [] because no split point T exists with S <= T < E
Examples
Input: ({'A': [1,2,3,6,7,10,11], 'B': [3,4,5,6,8,9,10,13], 'C': [7,8,9,10,11]}, 3, 11)
Expected Output: [['B', 'C']]
Explanation: B covers days 3 through 6 consecutively, and C covers days 7 through 11 consecutively, so splitting at T = 6 works. No other unordered pair covers the full range.
Input: ({'X': [1,2,3,4], 'Y': [2,3,4], 'Z': [1,2,3,4]}, 1, 4)
Expected Output: [['X', 'Y'], ['X', 'Z'], ['Y', 'Z']]
Explanation: X and Z each cover the whole range, while Y covers 2 through 4. X can pair with Y, Z can pair with Y, and X can pair with Z. This also covers the identical-availability case for X and Z.
Input: ({'H1': [1,2], 'H2': [4,5], 'H3': [2,3,4]}, 1, 5)
Expected Output: []
Explanation: No pair can cover every day from 1 through 5 consecutively. There is always a missing boundary day or an uncovered gap.
Input: ({'A': [5], 'B': [5], 'C': [4,5,6]}, 5, 5)
Expected Output: []
Explanation: The requested range has only one day, so there is no valid split point T with 5 <= T < 5.
Hints
- For each listing, compute how far it can cover consecutively starting from S, and how early it can cover consecutively ending at E.
- After that preprocessing, a pair is valid in O(1): one listing's prefix coverage must reach at least one day before the other listing's suffix coverage begins.