algorithm - 计算重叠日期范围时出现问题

Question

我在尝试找出正确的算法来计算一组日期范围时遇到了问题。

基本上我有一个无序日期范围列表(包含开始和结束时间数组的列表)，我想合并此列表，使其不包含重叠时间。

基本上合并两个日期范围:

if start1 <= end2 and start2 <= end1 //Indicates overlap
   if start2 < start1 //put the smallest time in start1
      start1 = start2
   endif
   if end2 > end1 //put the highest time in end1
      end1 = end2
   endif
endif

这连接了两个日期时间。

在遍历所有值时我遇到了绊脚石，所以最后的列表只包含不重叠的值。

我的函数式和递归编程有点生疏，欢迎任何帮助。

Answer 1

不要看区间，只看端点。

你有一堆开始的时刻和一堆结束的时刻。想象一下，开始时刻是红色的，结束时刻是蓝色的。或者想象开始时刻是开大括号，结束时刻是闭大括号。

将它们全部放在一个列表中。将列表从最早到最新排序，忽略颜色。

现在随身携带一个设置为零的计数器，然后沿着列表走下去。当您看到红色时刻时，增加计数器。当您看到蓝色时刻时，减少计数器。当计数器值从 0 变为 1 时，输出“开始”和当前时间。当计数器值从 1 变为 0 时，输出“结束”和当前时间。如果计数器值低于 0，输出“休斯顿，我们有问题”。您应该以 0 和一堆不错的非重叠间隔结束计数器。

这是很好的旧大括号计数算法。

插图。

 A bunch of overlapping intervals:

 (-------------------) 
                       (----------------------)           
                                                          (---)
       (---------------------)                       
                                                     (-----------------)

 A bunch of interval ends:

 (-----(-------------)-(-----)----------------)      (----(---)--------)