计算重叠日期范围的问题

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

这将合并两个日期时间。

在迭代所有值以使最终列表仅包含没有重叠的值时，我遇到了阻碍。

我的函数式和递归编程有点生疏，需要您的帮助。

- emt14

---

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 包含了一个解决方案和解释（好吧，这取决于你要优化什么，你没有具体说明..）。在FP中实现应该非常容易。 - Karoly Horvath

你能告诉我你所指的算法、数据结构或方法吗？ - emt14

我认为它在贪心算法部分的开头（虽然我不确定）。你必须先对列表进行排序。 - Karoly Horvath

你可以在这个链接中看到我的答案：http://stackoverflow.com/a/16961719/1534785 - Jeyhun Rahimov

Answer 1

不要看时间间隔，只看它们的结束时间点。

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

把它们全部放在一个列表中。忽略颜色，按从早到晚的顺序排序。

现在带着一个计数器为零，沿着列表走。当您看到一个红色时刻时，将计数器加1。当您看到一个蓝色时刻时，将计数器减1。当计数器值从0变为1时，输出“start”和当前时间。当计数器值从1变为0时，输出“end”和当前时间。如果计数器值低于0，则输出“Houston，我们有一个问题”。您应该以计数器为0和一堆漂亮的非重叠区间结束。

这就是经典的匹配括号算法。

图示。

 A bunch of overlapping intervals:

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

 A bunch of interval ends:

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

- n. m.

---

非常好用且实现起来非常简单。谢谢，我觉得我之前的方向不对！ - emt14

这个算法在我之前解决的一个问题中非常有效，那是在一个预订系统中计算资源分配的问题。目标是从一定数量的某些资源开始，并确定是否有人可以借出或预订总数的子集，前提是其他人以前已经做过同样的事情。 - Mirrana

非常有效且非常简单易行。 - undefined

Answer 2

n.m.的回答已经足够了，但如果你想使用你已经编写的代码，那么只需按开始时间对范围进行排序，然后遍历列表合并重叠部分即可。

- flight