algorithm - 如何从日期范围集中计算 "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是总的数量总结所有集合的范围。

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