查找多个列表中元素的重叠DateTime间隔

Question

我有一个n列表的构造,用于记录与我想要监视的事物(比如任务)相关的开始和结束时间.任务可以重复多次(尽管同一任务不能同时重叠/运行).每个任务都有一个唯一的ID,其开始/结束时间存储在自己的列表中.

我试图找到所有任务同时运行的时间段.

举个例子,下面我有3个任务; taskId 1发生7次,taskId 2发生两次,taskId 3发生一次;

import org.joda.time.DateTime
case class CVT(taskId: Int, begin: DateTime, end: DateTime)

val cvt1: CVT =  CVT (3, new DateTime(2015, 1, 1, 1, 0), new DateTime(2015, 1, 1, 20,0) )
val cvt2: CVT =  CVT (1, new DateTime(2015, 1, 1, 2, 0), new DateTime(2015, 1, 1, 3, 0) )
val cvt3: CVT =  CVT (1, new DateTime(2015, 1, 1, 4, 0), new DateTime(2015, 1, 1, 6, 0) )
val cvt4: CVT =  CVT (2, new DateTime(2015, 1, 1, 5, 0), new DateTime(2015, 1, 1, 11,0) )
val cvt5: CVT =  CVT (1, new DateTime(2015, 1, 1, 7, 0), new DateTime(2015, 1, 1, 8, 0) )
val cvt6: CVT =  CVT  (1, new DateTime(2015, 1, 1, 9, 0), new DateTime(2015, 1, 1, 10, 0) )
val cvt7: CVT =  CVT  (1, new DateTime(2015, 1, 1, 12, 0), new DateTime(2015, 1, 1, 14,0) )
val cvt8: CVT =  CVT  (2, new DateTime(2015, 1, 1, 13, 0), new DateTime(2015, 1, 1, 16,0) )
val cvt9: CVT =  CVT  (1, new DateTime(2015, 1, 1, 15, 0), new DateTime(2015, 1, 1, 17,0) )
val cvt10: CVT =  CVT  (1, new DateTime(2015, 1, 1, 18, 0), new DateTime(2015, 1, 1, 19,0) )

val combinedTasks: List[CVT] = List(cvt1, cvt2, cvt3, cvt4, cvt5, cvt6, cvt7, cvt8, cvt9, cvt10).sortBy(_.begin)

我想要的结果是:

CVT(123, DateTime(2015, 1, 1, 5, 0), DateTime(2005, 1, 1, 6 0) )
CVT(123, DateTime(2015, 1, 1, 7, 0), DateTime(2005, 1, 1, 8 0) )
CVT(123, DateTime(2015, 1, 1, 9, 0), DateTime(2005, 1, 1, 10 0) )
CVT(123, DateTime(2015, 1, 1, 13, 0), DateTime(2005, 1, 1, 14 0) )
CVT(123, DateTime(2015, 1, 1, 15, 0), DateTime(2005, 1, 1, 16 0) )

注意:我不介意结果中的'taskId'是什么,我只是显示'123'来尝试在这个例子中显示所有三个任务都在这些开始和结束时间之间运行.

我已经看过尝试使用递归fn和Joda Interval与.gap方法,但似乎无法找到解决方案.

关于如何实现我想要做的事情的任何提示都会很棒.

TKS

Answer 1

我在https://github.com/rklaehn/intervalset上找到了一组非重叠区间的库.它将在下一个版本的尖顶中

以下是如何使用它:

import org.joda.time.DateTime
import spire.algebra.Order
import spire.math.Interval
import spire.math.extras.interval.IntervalSeq

// define an order for DateTimes
implicit val dateTimeOrder = Order.from[DateTime](_ compareTo _)

// create three sets of DateTime intervals
val intervals = Map[Int, IntervalSeq[DateTime]](
  1 -> (IntervalSeq.empty |
    Interval(new DateTime(2015, 1, 1, 2, 0), new DateTime(2015, 1, 1, 3, 0)) |
    Interval(new DateTime(2015, 1, 1, 4, 0), new DateTime(2015, 1, 1, 6, 0)) |
    Interval(new DateTime(2015, 1, 1, 7, 0), new DateTime(2015, 1, 1, 8, 0)) |
    Interval(new DateTime(2015, 1, 1, 9, 0), new DateTime(2015, 1, 1, 10, 0)) |
    Interval(new DateTime(2015, 1, 1, 12, 0), new DateTime(2015, 1, 1, 14, 0)) |
    Interval(new DateTime(2015, 1, 1, 15, 0), new DateTime(2015, 1, 1, 17, 0)) |
    Interval(new DateTime(2015, 1, 1, 18, 0), new DateTime(2015, 1, 1, 19, 0))),
  2 -> (IntervalSeq.empty |
    Interval(new DateTime(2015, 1, 1, 5, 0), new DateTime(2015, 1, 1, 11, 0)) |
    Interval(new DateTime(2015, 1, 1, 13, 0), new DateTime(2015, 1, 1, 16, 0))),
  3 -> (IntervalSeq.empty |
    Interval(new DateTime(2015, 1, 1, 1, 0), new DateTime(2015, 1, 1, 20, 0))))

// calculate the intersection of all intervals
val result = intervals.values.foldLeft(IntervalSeq.all[DateTime])(_ & _)

// print the result
for (interval <- result.intervals)
  println(interval)

请注意,尖顶间隔比您可能需要的强大得多.它们区分开放和闭合间隔边界,并且可以处理无限间隔.但是,上面应该很快.