Split stay

给定 n 个 hotel，每个 hotel 对应一个列表，里面的数字代表房源空闲的日期，还有一个可以请求的日期范围 [start_date, end_date]。

然后把这个区间能够 split 成连续的两段，分别能够找到两个 hotel 来满足这个对应区间，且左右不能来回 overlapping（只能 forward）。要求返回对应的 hotel 组合，且不能重复。

简单版本

def find_hotel_pairs(hotels, start_date, end_date):
    """
    hotels: Dict[str, List[int]] -> { "Hotel1": [1, 2, 3], "Hotel2": [4, 5], ... }
    start_date: int
    end_date: int
    """
    # 1. 预处理：将日期列表转换为集合，提高查询效率
    hotel_sets = {name: set(dates) for name, dates in hotels.items()}
    hotel_names = list(hotels.keys())
    results = set()

    # 定义一个辅助函数，检查酒店是否覆盖特定闭区间
    def covers_range(hotel_name, s, e):
        s_set = hotel_sets[hotel_name]
        for d in range(s, e + 1):
            if d not in s_set:
                return False
        return True

    # 2. 枚举分割点 k
    # 目标区间被分为 [start_date, k] 和 [k + 1, end_date]
    for k in range(start_date, end_date):
        left_part_hotels = []
        right_part_hotels = []

        # 找出哪些酒店满足左半段，哪些满足右半段
        for name in hotel_names:
            if covers_range(name, start_date, k):
                left_part_hotels.append(name)
            if covers_range(name, k + 1, end_date):
                right_part_hotels.append(name)

        # 3. 组合满足条件的酒店对
        for h_a in left_part_hotels:
            for h_b in right_part_hotels:
                # 如果要求两家酒店不能是同一家，可以加上 if h_a != h_b
                results.add((h_a, h_b))

    return list(results)

# --- 测试用例 ---
hotels_data = {
    "Hotel_A": [10, 11, 12],
    "Hotel_B": [12, 13, 14, 15],
    "Hotel_C": [10, 11],
    "Hotel_D": [13, 14, 15]
}

start, end = 10, 15
pairs = find_hotel_pairs(hotels_data, start, end)

print(f"在区间 [{start}, {end}] 内满足条件的酒店组合有：")
for p in pairs:
    print(f"前半段: {p[0]}, 后半段: {p[1]}")

 

进阶版本

def find_hotel_pairs_optimized(hotels, start_date, end_date):
    hotel_sets = {name: set(dates) for name, dates in hotels.items()}
    
    # 记录哪些酒店能覆盖 [start_date, k]
    # left_reach[k] 存储所有能覆盖 start_date 到 k 的酒店名
    left_reach = {}
    # 记录哪些酒店能覆盖 [k, end_date]
    # right_reach[k] 存储所有能覆盖 k 到 end_date 的酒店名
    right_reach = {}

    total_range = range(start_date, end_date + 1)

    for name, dates_set in hotel_sets.items():
        # 1. 从左向右检查连续性
        for k in range(start_date, end_date):
            # 只有当 [start_date, k] 都在集合里，该酒店才符合前半段
            if all(d in dates_set for d in range(start_date, k + 1)):
                left_reach.setdefault(k, []).append(name)
            else:
                break # 一旦断开，更长的区间也不可能满足
        
        # 2. 从右向左检查连续性
        for k in range(end_date, start_date, -1):
            # 只有当 [k, end_date] 都在集合里，该酒店才符合后半段
            if all(d in dates_set for d in range(k, end_date + 1)):
                right_reach.setdefault(k, []).append(name)
            else:
                break

    # 3. 组合结果
    results = set()
    # 分割点 k 是前半段的终点，k+1 是后半段的起点
    for k in range(start_date, end_date):
        lefts = left_reach.get(k, [])
        rights = right_reach.get(k + 1, [])
        
        for h1 in lefts:
            for h2 in rights:
                results.add((h1, h2))

    return list(results)