Finding overlapping DateTime intervals of elements in multiple lists

Question

I have a construct of n lists that are being used to record the beginning and ending times associated with something I want to monitor (say a task). A task can be repeated multiple times (although the same task cannot overlap / run concurrently ). Each task has a unique id and its begin / end times are stored in it’s own list.

I’m trying to find the period of time where all tasks were running at the same time.

So as an example, below I have 3 tasks; taskId 1 happens 7 times, taskId 2 happens twice and taskId 3 happens only once;

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)

The result I’m trying to get is :

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) )

Note : I don’t mind what the ‘taskId’ is in the result, I’m just showing ‘123’ to try and show in this example that all three tasks were running between these start and end times.

I’ve looked at trying to use both a recursive fn and also the Joda Interval with the .gap method but can’t seem to find the solution.

Any tips on how I could achieve what I’m trying to do would be great.

Tks

Answer 1

Additionaly to Rüdiger 's library, which I believe is powerful, fast and extensible here is simple implementation using built-in collections lib.

I did redefine your CVT class reflecting ability to carry intersections as

case class CVT[Id](taskIds: Id, begin: DateTime, end: DateTime)

All you individual cvt defs now changed to

val cvtN: CVT[Int] = ???

We will try to catch events enters scope and leaves scope within our collection. For that algo we'll define following ADT:

sealed class Event
case object Enter extends Event
case object Leave extends Event

And corresponding ordering instances:

implicit val eventOrdering = Ordering.fromLessThan[Event](_ == Leave && _ == Enter)
implicit val dateTimeOrdering = Ordering.fromLessThan[DateTime](_ isBefore _)

Now we can write following

val combinedTasks: List[CVT[Set[Int]]] = List(cvt1, cvt2, cvt3, cvt4, cvt5, cvt6, cvt7, cvt8, cvt9, cvt10)
  .flatMap { case CVT(id, begin, end) => List((id, begin, Enter), (id, end, Leave)) }
  .sortBy { case (id, time, evt) => (time, evt: Event) }
  .foldLeft((Set.empty[Int], List.empty[CVT[Set[Int]]], DateTime.now())) { (state, event) =>
    val (active, accum, last) = state
    val (id, time, evt) = event
    evt match {
      case Enter => (active + id, accum, time)
      case Leave => (active - id, CVT(active, last, time) :: accum, time)
    }
  }._2.filter(_.taskIds == Set(1,2,3)).reverse

The most important here foldLeft part. After ordering events where Leaves are coming before Enterings, we are just carrying set of current working jobs from event to event, adding to this set when new job enters and capturing interval, using last entering time when some job leaves.

Answer 2

I got a library for sets of non-overlapping intervals at https://github.com/rklaehn/intervalset . It is going to be in the next version of spire

Here is how you would use it:

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)

Note that spire intervals are significantly more powerful than what you probably need. They distinguish between open and closed interval bounds, and can handle infinite intervals. But nevertheless the above should be pretty fast.