algorithm - 一种无需枚举天数即可计算外国人居住地的算法？

Question

我经常去的国家/地区的签证条件包括以下限制:

“您可以在任何 180 天的时间内在 [国家/地区] 最多居住 90 天”

给定一对日期(进入和退出日期)的暂定列表，是否有一种算法可以告诉我，对于每次访问，我是否会合规，以及有多少天？

显然，一种方法是构建大量单独的天数，然后沿着它滑动一个 180 天的窗口，计算居住天数。但我想知道是否有一种更优雅的方法，它不涉及构建一长串天数。

Answer 1

虽然它也可以看作是一维动态编程算法，但通常的算法基本上是一种贪心算法。基本上，不是一次滑动窗口 1 天，而是一次滑动 1 个开始日期。像这样:

first_interval = 0
last_interval = 0
for first_interval = 0 to N:
    # include more intervals as long as they (partially) fit within 180 days after the first one
    while last_interval < N and A[last_interval].start - A[first_interval].start < 180:
        last_interval += 1
    calculate total number of days in intervals, possibly clipping the last one

剪辑最后一个间隔的需要使得它不如其他方式那么优雅:在类似的算法中，不是每次都求和，而是将其添加到附加间隔(当递增 last_interval 时)并减去从它开始留守间隔(当递增 first_interval 时)。您可以在此处对倒数第二个间隔执行类似的操作，但除非您遇到严重的性能限制，否则最好不要这样做。