Compute split-stay listing pairs
Overview
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, 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].