沒有列舉天數的計算外國人居住地的算法？

Question

的，而我經常出差一個國家的簽證條件包括這個限制：

「你可能居住在[國家]最多的90天內，180任何時期」鑑於初步清單

成對的日期（進入和退出日期），有沒有一種算法可以告訴我，每次訪問時，我是否會進入或退出遵從狀態，以及有多少天？

顯然，做到這一點的一種方法是建立大量的單獨的日子，然後沿着它滑動180天的窗口，計算居住日期。但我想知道是否有一個更優雅的方法，不涉及建立一個很長的日子列表。

Answer 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++代碼計算兩個任意日期之間的持續時間，不早於O（1）時間的1月1日1 A.D.這是你在找什麼？

#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的算法。