1 def find_hotel_pairs(hotels, start_date, end_date):
 2     """
 3     hotels: Dict[str, List[int]] -> { "Hotel1": [1, 2, 3], "Hotel2": [4, 5], ... }
 4     start_date: int
 5     end_date: int
 6     """
 7     # 1. 预处理：将日期列表转换为集合，提高查询效率
 8     hotel_sets = {name: set(dates) for name, dates in hotels.items()}
 9     hotel_names = list(hotels.keys())
10     results = set()
11 
12     # 定义一个辅助函数，检查酒店是否覆盖特定闭区间
13     def covers_range(hotel_name, s, e):
14         s_set = hotel_sets[hotel_name]
15         for d in range(s, e + 1):
16             if d not in s_set:
17                 return False
18         return True
19 
20     # 2. 枚举分割点 k
21     # 目标区间被分为 [start_date, k] 和 [k + 1, end_date]
22     for k in range(start_date, end_date):
23         left_part_hotels = []
24         right_part_hotels = []
25 
26         # 找出哪些酒店满足左半段，哪些满足右半段
27         for name in hotel_names:
28             if covers_range(name, start_date, k):
29                 left_part_hotels.append(name)
30             if covers_range(name, k + 1, end_date):
31                 right_part_hotels.append(name)
32 
33         # 3. 组合满足条件的酒店对
34         for h_a in left_part_hotels:
35             for h_b in right_part_hotels:
36                 # 如果要求两家酒店不能是同一家，可以加上 if h_a != h_b
37                 results.add((h_a, h_b))
38 
39     return list(results)
40 
41 # --- 测试用例 ---
42 hotels_data = {
43     "Hotel_A": [10, 11, 12],
44     "Hotel_B": [12, 13, 14, 15],
45     "Hotel_C": [10, 11],
46     "Hotel_D": [13, 14, 15]
47 }
48 
49 start, end = 10, 15
50 pairs = find_hotel_pairs(hotels_data, start, end)
51 
52 print(f"在区间 [{start}, {end}] 内满足条件的酒店组合有：")
53 for p in pairs:
54     print(f"前半段: {p[0]}, 后半段: {p[1]}")

 1 def find_hotel_pairs_optimized(hotels, start_date, end_date):
 2     hotel_sets = {name: set(dates) for name, dates in hotels.items()}
 3     
 4     # 记录哪些酒店能覆盖 [start_date, k]
 5     # left_reach[k] 存储所有能覆盖 start_date 到 k 的酒店名
 6     left_reach = {}
 7     # 记录哪些酒店能覆盖 [k, end_date]
 8     # right_reach[k] 存储所有能覆盖 k 到 end_date 的酒店名
 9     right_reach = {}
10 
11     total_range = range(start_date, end_date + 1)
12 
13     for name, dates_set in hotel_sets.items():
14         # 1. 从左向右检查连续性
15         for k in range(start_date, end_date):
16             # 只有当 [start_date, k] 都在集合里，该酒店才符合前半段
17             if all(d in dates_set for d in range(start_date, k + 1)):
18                 left_reach.setdefault(k, []).append(name)
19             else:
20                 break # 一旦断开，更长的区间也不可能满足
21         
22         # 2. 从右向左检查连续性
23         for k in range(end_date, start_date, -1):
24             # 只有当 [k, end_date] 都在集合里，该酒店才符合后半段
25             if all(d in dates_set for d in range(k, end_date + 1)):
26                 right_reach.setdefault(k, []).append(name)
27             else:
28                 break
29 
30     # 3. 组合结果
31     results = set()
32     # 分割点 k 是前半段的终点，k+1 是后半段的起点
33     for k in range(start_date, end_date):
34         lefts = left_reach.get(k, [])
35         rights = right_reach.get(k + 1, [])
36         
37         for h1 in lefts:
38             for h2 in rights:
39                 results.add((h1, h2))
40 
41     return list(results)