空气床挂经

kratosyl 发表于 2025-8-7 01:39
我感觉是 当date range给出之后，每个listing最有左右两个连续的range，一个cover start date, 一个cover e ...

想一块去了。
建两个SortedList A和B
A存x，代表3～（x-1）available
B存y，代表y～11 available
第一步分析input
用二分找3，找到3往后数，发现到x-1之后就不连续了，存A（id，x）
再二分找11，找到11往前数，发现到y，存B（id，y）
第二步 寻找匹配
在B.Values里找A.Values[i] + 1，如果B.Values[j] = A.Values[i] + 1，则Airbnb A.Key[i] 可以匹配任意 Airbnb B.Key[0] ~ B.Key[j - 1]

两步都是O（nlogn），最差情况是O（n2）发生在全匹配时，发生在生成匹配结果的时候。

面試遇到這題，我只想放棄....

我问了一下chatGPT，他给了一个很好的角度。在最多的可能性下，答案的数量级是n^2，所以你不可能设计出时间复杂度低于这个的算法。（PS，可能的答案数量本质上是一个组合问题，从n个选项中选择2个出来，这种C n 2 问题的答案有 n*(n-1)/2 种）。

kratosyl 发表于 2025-8-7 11:09
我感觉是 当date range给出之后，每个listing最有左右两个连续的range，一个cover start date, 一个cover e ...

Worst case is: O(n*n)