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

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

## Answers ( 1 )

you could do this:

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:

`I.right < N.left`

, move to the left child`I.left > N.right`

, move to the right childbecause 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.