Split Stay Combinations

Based on my comprehensive research, I can now generate the problem statement. The "Split Stay Combinations" problem most closely aligns with the "Generate split-stay pairs efficiently" problem from PracHub with the tags you specified.

Problem Description

You are building an algorithmic service for Airbnb's split-stay feature. Given a set of listings with their availability windows and a guest's requested date range, identify all valid pairs of listings that can seamlessly cover the entire stay. A split stay occurs when a guest stays in one listing for the first portion of their trip, then transitions to a different listing for the remainder—with exactly one transition point between them.

The challenge lies in efficiently pairing listings without redundant iteration, while handling sparse availability data and optimizing for scalability across large inventory sets.

Input/Output Format

Input:

listings: List of N listings, where each listing is represented as an object or dictionary containing:
- id: Integer identifier for the listing (0-indexed)
- availability: Sorted list of integer day numbers indicating available dates (e.g., days since epoch)
L: Integer representing the inclusive start day of the requested date range
R: Integer representing the inclusive end day of the requested date range (L < R)

Output:

A list of ordered pairs (X, Y) of distinct listing indices, where:
- Listing X is available for all days in [L, s] for some split point s
- Listing Y is available for all days in [s+1, R] for the same split point s
- L ≤ s < R (the split point must create two non-empty segments)
Return format: List[Tuple[int, int]] representing all valid listing pairs
Order: Pairs should be ordered by (X, Y) lexicographically

Data Types:

N: 1 ≤ N ≤ 10^5 (number of listings)
Date range: 1 ≤ L < R ≤ 10^6
Each availability array: size up to 10^5 elements (worst case: listing available every day in range)

Examples

Example 1

Input: listings = [ {id: 0, availability: [1, 2, 3, 6, 7, 10, 11]}, {id: 1, availability: [3, 4, 5, 6, 8, 9, 10, 13]}, {id: 2, availability: [7, 8, 9, 10, 11]} ] L = 3 R = 11

Output: [(1, 2)]

Explanation:

For split point s = 6:
- Listing 1 is available for ✓ (covers )[1][2][3][4]
- Listing 2 is available for ✓ (covers )[5][6][7][8][9]
- This forms a valid pair covering the entire range[9][1]
Other combinations fail:
- Listings 0 and 1: Listing 0 cannot cover through day 11 (ends at 11 but has gap at day 8-9)
- Listings 0 and 2: Listing 0 cannot cover through day 5 (has gaps)

Example 2

Input: listings = [ {id: 0, availability: [1, 2, 3, 4, 5]}, {id: 1, availability: [5, 6, 7, 8, 9]}, {id: 2, availability: [1, 2, 3, 4, 5, 6, 7, 8, 9]} ] L = 1 R = 9

Output: [(0, 1)]

Explanation:

For split point s = 5:
- Listing 0 covers ✓[2][3][10][11][1]
- Listing 1 covers —but we need only (since 5 was end of first segment), actually Listing 1 does cover ✓[3][4][6][7][5]
- Valid pair (0, 1)
Note: Listing 2 alone can cover the entire range, but the problem asks for split-stay pairs (two different listings)

Constraints

Time Complexity Target: O(L · R · log N) or better; specifically better than the naive O(L^2 · R) where L = number of listings and R = date range span
Space Complexity Target: O(L + R) for data structures; avoid storing all possible pairs explicitly in naive manner
Edge Cases to Handle:
1. No valid pairs exist (return empty list)
2. Availability gaps: Listing availability must be fully contiguous for the assigned segment (no breaks allowed)
3. Missing boundary days: A listing must include both the first and last day of its assigned segment
4. Identical availability: Two listings with the same availability can form valid pairs at all possible split points
5. Large date ranges: Efficiently handle R - L up to 10^6 without iterating through every date individually
6. Single listing available: If only one listing covers the full range, it cannot form a split-stay pair

Solution Hint

Use a two-pointer/binary search approach combined with greedy split-point selection: For each candidate pair of listings (X, Y), binary search to find all feasible split points s where X continuously covers [L, s] and Y continuously covers [s+1, R]. Optimize by preprocessing each listing's availability into interval segments, then checking segment boundaries rather than individual days. A bitmask or bitset can efficiently track which listings can cover specific segment ranges, enabling fast filtering of candidate pairs before performing detailed interval validation.