How to find intersections among N time intervals?

Question

Algorithms

There are N time periods, of the form

[{
    "id": 1,
    "start": "2018-08-07 06:00:00+0000",
    "end": "2018-08-07 06:15:00+0000"
}, {
    "id": 2,
    "start": "2018-08-07 06:15:00+0000",
    "end": "2018-08-07 06:45:00+0000"
}, {
    "id": 3,
    "start": "2018-08-07 06:25:00+0000",
    "end": "2018-08-07 06:35:00+0000"
}, {
    "id": 4,
    "start": "2018-08-07 06:10:00+0000",
    "end": "2018-08-07 06:30:00+0000"
}]

Is there an algorithm of less complexity than N^(N-1) to find that id=3 intersects id=2 in time and id=4 intersects id in (1,2,3)?

Answer 1

It is necessary to sort events of the form by time {id: 2, type: "start"}or {id: 4, type: "end"}
Iterate through these times once, moving one at a time, and keeping track of the current window: who is in it. From this it is clear who crossed with whom.

Answer 2

https://habr.com/post/209138/