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

Examples

Solution

def solution(avail, start_date, end_date):
    n = len(avail)

    # Need two non-empty contiguous segments, so at least two dates are required.
    if n < 2 or start_date >= end_date:
        return []

    # left_end[i] = largest date x such that hotel i covers every date in [start_date, x]
    # If hotel i does not cover start_date, left_end[i] will stay start_date - 1.
    left_end = [start_date - 1] * n

    # right_start[i] = smallest date x such that hotel i covers every date in [x, end_date]
    # If hotel i does not cover end_date, right_start[i] will stay end_date + 1.
    right_start = [end_date + 1] * n

    for i, days in enumerate(avail):
        day_set = set(days)  # removes duplicates and allows O(1) average membership checks

        d = start_date
        while d <= end_date and d in day_set:
            left_end[i] = d
            d += 1

        d = end_date
        while d >= start_date and d in day_set:
            right_start[i] = d
            d -= 1

    ans = []

    # Generate results in required order: s ascending, then A ascending, then B ascending.
    for s in range(start_date, end_date):
        left_hotels = []
        right_hotels = []

        for i in range(n):
            if left_end[i] >= s:
                left_hotels.append(i)
            if right_start[i] <= s + 1:
                right_hotels.append(i)

        for a in left_hotels:
            for b in right_hotels:
                if a != b:
                    ans.append((a, b, s))

    return ans

Time complexity: O(T + n * R + K), where `T` is the total number of availability entries, `R = end_date - start_date + 1`, and `K` is the number of returned tuples. Space complexity: O(n + M + K), where `M` is the maximum number of unique dates in a single hotel's availability list and `K` is the size of the returned result.

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.