如何根据日期范围集计算 "Outersections"

Question

考虑一组日期范围列表：

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}]

是否有计算 "Outersection" 间隔的有效方法（阴影区域，A、B、C 日期范围之间没有交集）？

编辑： @kaidul-islam，感谢您的回答！我将逻辑简化为一个 for 和一个 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)
        }
    }
}

我错过了什么？

PS：范围按左右日期排序。

Answer 1

根据左侧日期的升序对所有范围集（A、B 和 C 进行排序（左侧日期较小的范围排在最前面） .

然后按照这个伪代码：

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

排序的时间复杂度为 O(nlogn)，从左到右扫描的时间复杂度为 O(n)，其中 n 是所有集合的范围总数。

如果您需要任何帮助，请告诉我。

如何根据日期范围集计算 "Outersections"

How to calculate "Outersections" from Sets of date range

algorithm

date-range

set-theory