Airbnb电面挂经

Recruiter reach out. 我就随便面面，没时间刷题。果然就没面过电面。Recruiter竟然没有介绍职位是什么。
题目原文没来及保存，大致说一下总体的结构。

用户订Airbnb的时候，如果所选的行程没有一个连续available的Airbnb，那么可以把行程拆成两段，分别住在两个Airbnb里。输入有两个，第一个是一系列Airbnb的availability, 第二个是用户行程的起止日期。输出所有可行的行程组合。输入里的数字可以视为是抽象的日期，不用考虑现实中的日月。

Input:
airbnbs = {
  "Airbnb A": [1, 2, 3, 5, 6, 9, 10],
  "Airbnb B": [3, 4, 5, 6, 9, 10],
  "Airbnb C": [7, 8, 9, 10, 11],
}
dates = [3, 11]
Output:
results = ["Airbnb B", "Airbnb C"]

一开始写了一大堆啰嗦的代码，没跑对。后来面试官提示了一下，因为行程最多分成两段，所以第一段必然要包含起始日期，第二段必然要包含结尾日期。按照这种思路，解法是先找出所有包含起始日期的Airbnb, 再找出所有包含结尾日期的Airbnb, 然后两两组合，找出组合起来两段能接上（也可以有重叠）的组合。不过这应该不是最优解。面试官也不置可否。

后来让AI写了一下，Claude直接给了一种看似暴力但很简洁的方法，用set存availability, 然后做并集，看是否覆盖行程的起止日期。片段如下，

two_airbnb_solutions = []
airbnb_names = list(airbnbs.keys())
    
for i in range(len(airbnb_names)):
    for j in range(i + 1, len(airbnb_names)):
        airbnb1 = airbnb_names[i]
        airbnb2 = airbnb_names[j]
            
        combined_days = set(airbnbs[airbnb1]) | set(airbnbs[airbnb2])
        if travel_days.issubset(combined_days):
            two_airbnb_solutions.append((airbnb1, airbnb2))

但是这个解法的时间复杂度貌似也是O(n^2)的，暂时没有想到什么更好的方法。如果评论区有大佬想到，请指教。