Compute split-stay listing pairs

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].

Compute Split-Stay Listing Pairs

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:

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.

Examples

Example 1

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)
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.

Example 2

Input: ({'X': [1,2,3,4], 'Y': [2,3,4], 'Z': [1,2,3,4]}, 1, 4)
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.

Hints

1. For each listing, compute how far it can cover consecutively starting from S, and how early it can cover consecutively ending at E.
2. 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.

Approach

Key idea. A split stay needs one listing to cover a consecutive prefix [S..T] and another to cover a consecutive suffix [T+1..E], with S <= T < E. Instead of testing every split point per pair, we reduce each listing to two numbers and compare those.

Per-listing reduction (O(A) total).

• prefix_end(days): starting at day S, walk forward while days are consecutive (d == prev+1), skipping duplicates and stopping past E. It returns the largest T such that the listing is available on every day S..T. If the listing isn't even available on S, it returns S-1.
• suffix_start(days): symmetric from E backward — returns the smallest T such that the listing covers every day T..E, or E+1 if day E is missing.

These scan each availability list once, so all listings cost O(A) combined.

Pairing. Sort the IDs (so output is lexicographic and each unordered pair is emitted once via the i < j loop). For ordered roles a then b, a valid split exists iff:

• pref[a] >= S (a actually covers from S),
• pref[a] + 1 >= suff[b] (a's prefix reaches at least to where b's suffix can begin, so a real split point exists; overlap is allowed).

Each pair is checked in both orders (a_then_b or b_then_a). If either works, [a, b] is added. The S >= E and < 2 listings guards return [] immediately, correctly handling S == E.

Why correct: consecutive prefix/suffix lengths fully characterize each listing's usefulness, and pref[a]+1 >= suff[b] is exactly the condition for a gap-free split point in [S, E).

• Time complexity: O(A + L^2), where A is the total number of availability entries across all listings and L is the number of listings. Each listing's prefix/suffix scan is linear in its own list (O(A) summed); the pairwise check loop is O(L^2). Sorting IDs adds O(L log L), dominated by L^2.
• Space complexity: O(L), excluding the output. Two dicts (pref, suff) and the sorted id list each hold L entries; the per-listing scans use O(1) extra space.