Как найти пересечения среди N временных отрезков?

Question

[Андрей]

Есть N временных отрезков, вида

[{
    "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"
}]

Есть ли алгоритм меньшей сложности, чем N^(N-1), чтобы найти то, что id=3 пересекается по времени с id=2, а id=4 пересекается с id in (1,2,3)?

Answer 1

[Сергей Соколов]

Надо отсортировать по времени события вида {id: 2, type: "start"} или {id: 4, type: "end"}
Один раз перебрать эти времена, двигаясь по одному, и отслеживая текущее окно: кто в нём. Из этого понятно, кто с кем пересекся.

Comments

[Андрей]

тогда, наверное, будет лучше все эти времена заинсертить в sqlite в tmpfs, получить все записи и последовательно пройтись по ним запросом типа

select id from id != $current_id and ( (start between $current_start and $current_end) or  (end between $current_start and $current_end)  )

?

Answer 2

[Алексей Шашенков]

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