Find hotel pairs to cover a split stay

You are implementing a simplified “split stay” feature.

Problem

You are given:

• n hotels (or listings), indexed 0..n-1.
• For each hotel i, an unsorted list avail[i] of integer dates (e.g., days since epoch) indicating the dates that hotel is available.
• A requested inclusive date range [start_date, end_date].

A split stay means the guest stays in two different hotels in two contiguous, non-empty segments that exactly cover the requested range:

• Choose a split point s such that start_date ≤ s < end_date.
• Hotel A must be available for every date in [start_date, s].
• Hotel B must be available for every date in [s+1, end_date].
• The stay is “forward only”: the first segment is earlier than the second; no interleaving/overlap beyond the shared boundary between s and s+1.
• Hotels must be different: A != B.

Output

Return all distinct valid combinations as tuples: (A, B, s) meaning hotel A covers the left segment [start_date, s] and hotel B covers the right segment [s+1, end_date].

Notes:

• If avail[i] contains duplicates, they should not create duplicate output tuples.
• If no split stay is possible, return an empty list.

Example (informal)

If [start_date, end_date] = [10, 13] and a split s=11 is chosen, then hotel A must cover dates {10,11} and hotel B must cover {12,13}.

Find Hotel Pairs to Cover a Split Stay

You are implementing a simplified split-stay feature.

You are given n hotels, indexed 0..n-1. For each hotel i, avail[i] is an unsorted list of integer dates on which that hotel is available. You are also given an inclusive requested date range [start_date, end_date].

A valid split stay uses exactly two different hotels and exactly one split point s such that start_date <= s < end_date:

• Hotel A covers every date in [start_date, s]
• Hotel B covers every date in [s+1, end_date]
• Both segments must be non-empty
• A != B

Return all distinct valid tuples (A, B, s), where hotel A covers the left segment and hotel B covers the right segment.

Important details:

• avail[i] may be unsorted and may contain duplicates.
• Duplicates in avail[i] must not create duplicate output tuples.
• Return the result sorted by split point s ascending, then by A ascending, then by B ascending.
• If no valid split stay exists, return an empty list.

Constraints

• 1 <= len(avail) <= 2000
• 0 <= sum(len(hotel_dates) for hotel_dates in avail) <= 2 * 10^5
• -10^9 <= each date <= 10^9
• start_date <= end_date
• 0 <= end_date - start_date <= 2000
• The total number of valid output tuples fits in memory

Hints

1. For each hotel, you do not need every possible split explicitly. It is enough to know how far it can continuously cover starting from start_date, and how early it can continuously cover backward from end_date.
2. Once you know which hotels can cover the left side and which can cover the right side for a split s, generate all pairs except those where the two hotel indices are the same.