Тренировки по алгоритмам от Яндекса. Лекция 7: «Сортировка событий»

[@uliana7851]

0:39 - Сортировка событий 2:00 - События 4:12 - задача 1 4:58 - решение задачи 1 12:55 - Задача 2 13:05 - решение задачи 2 18:04 - задача 3 18:47 - решение задачи 3 26:13 - События на круге 36:40 - задача 4 на два прохода 37:20 - парковка в течение дня 39:30 - решение задачи 4 43:18 - задача 5 44:05 - решение задачи 5 45:57 - Задача 6 46:20 - неэффективное решение 53:15 - эффективное решение 55:05 - про предстоящее домашнее задание 55:32 - ответы на вопросы

[@egorkalmykov4003]

Спасибо огромное за полезную и информативную лекцию !!!

[@ИванГончаров-ц8й]

Спасибо большое! Очень полезный материал

[@floppa-fy2qh]

Для "циклических событий" разве не удобнее сделать некоторый препроцессинг во время сортировки: bool intersectMidnight = tOut < tIn if (intersectMidnight) tOut += midnightDuration Ну то есть, если отрезок пересекает круг в месте, где он зацикливается (полночь в данном случае), то просто прибаляем к концу отрезка длину цикла В случае с задачей на max количество открытых касс этого достаточно, а в случае с количеством отрезков, когда все работники на работе ещё придётся по модулю midnightDuration считать Но как по мне это проще тех 2-х представленных способов

[@ReAgent003]

Для справки: алгоритм называется "метод сканирующей прямой"

[@nicholasdymov2962]

25:04 С приходом начальника всё стало работать медленнее. Как символично... 😊

[@АлександрИлюхин_2002]

16:27 2 задача, но ведь лучше вычислять сразу большой отрезок до нуля, а не каждый раз когда кто-то входит или выходит 35:20, но если один и тот же сотрудник был 2 раза на работе за день, к примеру: он вернулся на работу из-за забытого зонта. Тогда уже максимумов на круге может быть бесконечность. То же касается и отрезков.

[@GreatVolcano]

Для 2-й задачи - попробуйте интервал n = 2, t_in = [1,10], t_out = [2, 11]. Должна получиться сумма 2

[@GreatVolcano]

Вчитался и понял ваше решение. Да, мне сначала тоже показалось, что лучше просто добавлять сумму, если online = 0. Решение тож норм

[@tadpole1019]

Задачи про парковку в разделе два прохода, но в решении совершается один проход, то есть задачи вырождаются в задачи на отрезке и мы никак не учитываем машины на парковке, которые могли остаться стоять с прошлого дня, и события их отъезда. Или я что-то не так понял?

[@ReAgent003]

18:02 в пятой строке с конца `if events[i][1] == -1` ошибка? Разве не должно быть == 1?

[@ДмитрийВасильевич1234]

- 1 это событие означающие что человек зашел на сайт, а 1 означает что человек вышел с сайта.

[@ReAgent003]

@@ДмитрийВасильевич1234 да, согласен

[@TheVenom20003]

11:47 а зачем надо было сортировать , не понял

[@zarinali1950]

А на java вместо Pair какую структуру нужно использовать? Map-ы? Но они не всегда подходят

[@dibehemoth401]

Свою Pair написать.

[@zarinali1950]

@@dibehemoth401 ☹️

[@muznadzor554]

Map.Entry

[@walclow8247]

своя pair за 0 секунд пишется, если без generics, хотя и там тоже говно вопрос

[@kudryashovda]

А бот с подсказками еще работает? Если да, то пришлите пожалуйста ссылку.