scala - 查找多个列表中元素的重叠日期时间间隔

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 方法，但似乎找不到解决方案。

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

感谢

Answer 1

我在 https://github.com/rklaehn/intervalset 得到了一个用于非重叠间隔集的库.它将出现在下一版本的 spire 中

以下是您将如何使用它:

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)

请注意，尖顶间隔比您可能需要的要强大得多。它们区分开区间和闭区间边界，并且可以处理无限区间。但尽管如此，上面的代码应该还是相当快的。