计算重叠日期范围的问题

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时,输出"start"和当前时间.当计数器值从1变为0时,输出"结束"和当前时间.如果计数器值低于0,则输出"休斯顿,我们遇到问题".你应该用你的计数器结束0和一堆很好的非重叠间隔.

这是一个很好的旧支撑计数算法.

插图.

 A bunch of overlapping intervals:

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

 A bunch of interval ends:

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