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

Question

我经常去的国家的签证条件包括以下限制：

"You may reside in [country] for a maximum of 90 days in any period of 180"

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

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

Answer 1

虽然它也可以被看作是一维动态编程算法，但通常的算法基本上是一个贪心算法。基本上，不是一次滑动 window 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 时）。您可以在此处对倒数第二个间隔执行类似的操作，但除非您遇到严重的性能限制，否则最好不要这样做。

Answer 2

以下 C++ 代码计算不早于 1 月 1 日 A.D 的两个任意日期之间的持续时间。在 O(1) 时间内。这是您要找的吗？

#include <iostream>
using namespace std;

int days(int y,int m,int d){
    int i,s,n[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    y+=(m-1)/12; m=(m-1)%12+1; if(m<1) {y--; m+=12;}
    y--; s=y*365+y/4-y/100+y/400; y++;
    if(y%4==0 && y%100 || y%400==0) n[2]++;
    for(i=1;i<m;i++) s+=n[i]; s+=d; return s;
}
int main(){
    cout<<days(2017,8,14)-days(2005,2,28)<<endl;
    return 0;
}

您可以使用days()函数将所有进出日期映射为整数，然后使用Sneftel算法。

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

An algorithm to calculate foreign residence without enumerating days?

algorithm

days