VladimirAndreev
@VladimirAndreev
php web dev

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

Есть 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)?
  • Вопрос задан
  • 366 просмотров
Решения вопроса 1
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Надо отсортировать по времени события вида {id: 2, type: "start"} или {id: 4, type: "end"}
Один раз перебрать эти времена, двигаясь по одному, и отслеживая текущее окно: кто в нём. Из этого понятно, кто с кем пересекся.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
teknik2008
@teknik2008
Расскажите про GOLANG. Мне интересно
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы