Algorithm: How to re-arrange a time-range event (interval) list based on wether time events overlap, faster than O(n^2)?

Question

Let's say I have an array of time ranges like so:

[
  { name: 'A', startTime: '10:15', endTime: '11:15'},
  { name: 'B', startTime: '10:45', endTime: '14:15'},
  { name: 'C', startTime: '15:35', endTime: '16:15'},
  { name: 'D', startTime: '11:30', endTime: '16:20'},
  { name: 'E', startTime: '10:30', endTime: '18:00'},
]

which looks like this (visually):

|---A---|________________________________________________________________

_____|------B------|_____________________________________________________

________________________|----C----|______________________________________

___________|-----------D-----------|_____________________________________

___|-------------------E---------------------|___________________________

I wan't to arrange the intervals in a way that will result in an array of arrays so that:

  • Each interval of an array, does not intersect with ANY other interval in that array.

(Visual representation of what the end result might look like):

[
   [ A, D ],
   [ B, C ],
   [ E ]
]
  • The total number of arrays is absolutely the minimum number possible.

(by that I mean, if an element does intersect with the first array, but not the second array created, don't create a third array put it in the second one)

  • If a new interval intersects an interval that's already in the first array, the one that will be kept within the first array will be the one with the lowest startTime. The other one will be put on next available array, if it doesn't intersect with any interval in there, otherwise on a new one.

  • Performance is needed (The easiest way would be to iterate through every element to decide if it intersects, but that would be consuming resources like crazy) so something better than O(N^2) would be preferable.

Any ideas? Thank you.


Show source
| sorting   | arrays   | overlap   | algorithm   | graph-algorithm   2016-12-07 22:12 1 Answers

Answers ( 1 )

  1. 2016-12-08 02:12

    you could do this:

    1. put the fist interval in set A0
    2. take the second interval. If it doesn't intersect intervals in a set, put it in such set, if it does consider the next set. if it intersects all sets, create a new one and put it there.

    With a naive implementation of checking for interval intesection with set, this is O(N^2). However, for each set we can maintain a binary tree sorting intervals. Because intervals in a set do not intersect, there is a full ordering between them. This way, to check if an interval I intersects an interval in the tree, we can traverse the tree as follows:

    • if I intersects the current node N, return true
    • if I.right < N.left, move to the left child
    • if I.left > N.right, move to the right child

    because we can traverse the tree in log(M) steps (where M is the size of the set, we get O(N x (N / M) x logM). If no interval overlaps, this is O(N x logN). If all intervals overlap, this becomes O(N x N). To further improve this worst case, you could organize the trees in a binary tree, Interval Tree or Augmented Tree (see https://en.wikipedia.org/wiki/Interval_tree), so that not all sets need to be traversed.

◀ Go back