Comment calculer « Outersections » à partir de jeux de plage de dates

Question

Tenir compte une liste d'ensembles de plages de dates:

A: [{2017/01/01, 2017/01/30},{2017/02/15, 2017/03/05},{2017/03/25, 2017/04/30}] 

B: [{2017/01/01, 2017/01/30}] 

C: [{2017/01/01, 2017/01/20},{2017/02/19, 2017/03/15}] 

Yat-il un moyen efficace de calculer les intervalles « Outersection » (zone hachurée , sans intersections entre les plages de dates A, B, C)?

EDIT: @ kaidul-islam, merci pour votre réponse! J'ai simplifié la logique dans un for et un if:

... 
for (i; i < n - 1; i++) { 
    var current := ranges[i]; 
    var next := ranges[i + 1]; 

    if (next.left > current.right) { 
     gap := next.left - right 
     if(gap > 0){ 
      result.add(gap) 
     } 
    } 
} 

je raté quelque chose? PS: les plages sont triées par date de gauche et de droite.

Answer 1

Trier tout l'ensemble des gammes (A, ainsi B et C) selon l'ordre croissant de la date à gauche (plage plus petite avec la date à la position gauche viendra en premier).

Et puis suivez ce pseudo-code:

result = [] 
left := range[0].left 
right := range[0].right 
i := 0 
while(i < n): 

    while(i + 1 < n && ranges[i + 1].left <= right): 
     right := max(ranges[i + 1].right, right) 
     i := i + 1 
    end 

    if(i + 1 < n): 
     gap := ranges[i + 1].left - right 
     if(gap > 0): 
      result.add(gap) 
     endif 
    endif 

end 

return result 

complexité du temps est O(nlogn) pour le tri et O(n) pour gauche à droite où scan n est le nombre total de gammes additionnant tous ensembles.

Faites-moi savoir si vous avez besoin d'aide.