Split stays across two listings

A vacation rental site wants to offer split stays: when no single home is free for a guest's whole trip, the guest stays in one home first and then moves to another.

There are n listings, numbered 0 to n - 1. listings[i] is the list of days (integers) on which listing i is free. A guest asks for every day from start to end, inclusive.

Implement:

def split_stays(listings: list[list[int]], start: int, end: int) -> list[tuple[int, ...]]

Return every way to cover the whole range:

• Single: (i,) when listing i is free on every day from start to end.
• Split stay: (a, b) with a != b when there is a day t with start <= t < end such that listing a is free on every day of start..t and listing b is free on every day of t+1..end. Pairs are ordered: (a, b) means a first. Report each pair once, even when several split days work.

Return the singles first, sorted, then the pairs, sorted. A one-day request has no split stays.

Constraints: 1 <= n <= 10^4, the range is at most 365 days long, and the days in each list are distinct but may be in any order. Aim for better than checking every pair at every split day.

Example 1

listings = [[3, 4], [5, 6, 7], [1, 2, 3, 4, 5, 6], [4, 5, 6]]
start = 3, end = 6
-> [(2,), (0, 1), (0, 2), (0, 3), (2, 1), (2, 3)]

Listing 2 covers days 3 to 6 on its own. Listing 0 covers days 3 and 4, and listings 1, 2 and 3 each cover days 5 and 6. Listing 2 can also come first, followed by listing 1 or 3. (1, 0) does not work, because listing 1 is not free on day 3.

Example 2

listings = [[10, 12], [11, 13]]
start = 10, end = 13
-> []

Each listing has a gap, and neither one's run of free days reaches the other's.