Un algorithme pour calculer la résidence étrangère sans énumérer les jours?

Question

Les conditions de visa pour un pays auquel je voyage incluent souvent cette restriction:

« Vous pouvez résider dans [pays] pour un maximum de 90 jours dans une période de 180 »

Étant donné une liste indicative des paires de dates (dates d'entrée et de sortie), y a-t-il un algorithme qui peut me dire, pour chaque visite, si je serai en conformité ou non, et de combien de jours? De toute évidence, une façon de le faire consisterait à créer un grand nombre de jours individuels, puis à faire glisser une fenêtre de 180 jours le long de celle-ci, en comptant les jours de résidence. Mais je me demande s'il existe une méthode plus élégante qui n'implique pas la construction d'une longue liste de jours.

Answer 1

L'algorithme normal pour ceci est fondamentalement un algorithme glouton, bien qu'il puisse également être vu comme un algorithme de progamming dynamique 1D. Fondamentalement, plutôt que de glisser la fenêtre 1 jour à la fois, vous faites glisser 1 date de départ à la fois. Comme si:

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 

La nécessité de couper le dernier intervalle le rend un peu moins élégant que pourrait autrement: dans les algorithmes similaires, plutôt que de sommer le total à chaque fois, vous ajoutez à cela pour des intervalles sur ajouté (lors de l'incrémentation de last_interval) et soustrait de celui-ci pour les intervalles laissés en arrière (lors de l'incrémentation de first_interval). Vous pourriez faire quelque chose de similaire ici avec l'avant-dernier intervalle, mais à moins que vous ne soyez sérieusement impliqué dans une performance, il est probablement préférable de ne pas le faire.

Answer 2

Le code C++ suivant calcule la durée entre deux dates arbitraires au plus tôt Jan 1, 1 A.D. en O (1). Est-ce ce que vous cherchez?

#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; 
} 

Vous pouvez utiliser la fonction days() pour cartographier toutes les dates d'entrée et de sortie sur les entiers, puis utiliser l'algorithme du Sneftel.