1. Забудь про insert в лист) Если тебе нужно сделать инсерт, ты что-то делаешь не так, асимптотика вставки O(длина листа). Либо передалай алгоритм, чтобы инсерт тебе был не нужен, либо использую хештаблицы/линкед листы/деревья поиска, в общем то, что подходит для быстрой вставки в рандомный индекс. 2. Возможно, в задачке подразумевалось, что интервалы могут пересекаться, иначе задачка слишком простая выходит. 3. Можешь такие задачки засовывать в какой-нибудь класс, конструктор на входе берет лист, по методу free_intervals возвращает свободные интервалы. Мб кто-то оценит) Я бы посортил вход по левой границе, прошел указателем по массиву и на лету сконструировал свободные интервалы. Крайние случаи: пересечение интервалом точки 00:00 и вложенность одного интервала в другой (если допускаются пересечения), их не сложно обработать. Успехов!
вопрос по первому пункту. я не шарю но разве чтобы вставить элемент в какой то индекс в связном списке не нужно для начала пройтись по этому листу до определенного индекса?
@@pslups9086, да, нужно скопировать в новый массив то, что было до этого элемента, потом добавить элемент, скопировать то, что после элемента, итого получается используется О(n) по времени для обхода списка и O(1) для операции вставки нового
2-3 недели обучаюсь программированию. Чето пересечения и вложенности не могу придумать как обработать. Создал функцию на проверку пересечения для 2х списков - на выходе True/False. Понятно, что и при пересечении, и при вложенности надо возвращать одно и тоже (минимальный из первых элементов двух списков и максимальных из вторых элементов). Но как это сделать? Допустим, я начал проверять каждый с каждым (кроме себя и предыдущих). Первый список ни с кем не пересекся - я его добавляю в новый список. Второй пересекся с 3им - добавляю их объединение, а если 3ий потом пересечется с 4ым??? На выходе опять будут пересекающиеся интервалы... Ну, можно ещё раз функцией прогнать - а сколько раз? Рекурсию чтоль жахнуть с остановкой, когда итоговый список вернет сам себя? Вот пока писал комментарий придумал чето)) Сча попробую. UPD. Еле-еле получилось, но работает правильно, только если сквозь 00-00 изначально проходит не больше одного промежутка.
@@RANETKA234 Уберем отрезки, пересекающие точку 00-00, потом обработаем их отдельно. Создадим массив пар (время события, тип события), где события бывают 2-ух типов: кто-то занял кабинет и кто-то перестал занимать кабинет. Отсортируем этот массив по возрастанию и пройдем по нему циклом: заведем переменную counter = 0, если встречаем событие кабинет занят, то counter++, если событие кабинет перестал быть занят, то counter--. В итоге кабинет занят только тогда, когда counter > 0. Если counter становится равным 0, то промежуток от текущей точки до предыдущей, когда counter был равен нулю - промежуток, где кабинет занят. Остается сохранить такие промежутки, можно прямо в этом же цикле. Из них уже можно просто получить промежутки, когда кабинет свободен. Отрезки, пересекающие 00-00 можно обработать все разом, пройдя по ним циклом и найдя минимальный левый и максимальный правый концы, тогда отрезки от максимального левого до 0 и от 0 до макисмального правого заняты. Асимптотика O(n logn), где n длина списка с промежутками. Вообще решения такого типа называются "сканирующая прямая", можешь погуглить.
А не лучше , чем в цикл в цикле интервалов перебирать, просто на основе листа [[a,b],..,[y,z]] создать лист [[0,a],[b,c],..,[x,y],[z,1440] в одном цикле путем последовательного присвоения, или это дольше работать будет?
Не знаю, может и лучше, пока не увидел код, не могу сказать:) Вообще, нет ничего страшного во вложенных for, потому что если мы знаем, что у нас маленький список, например, 5 элементов, и мы пройдемся по нему 2 раза - for for, то будет 25 итераций, а если список будет из 30-ти элементов и мы пройдёмся по нему 1 раз - один for, то итерацией все равно будет больше. На видео внутренний цикл проходит по 2 элементам)
Тайп хинты) -> говорит о том, какого типа данные функция вернёт, в python это что-то вроде фейка, пока что, разве что расширение какое-нибудь для IDE будет подсвечивать некорректное использование типов. Также знаю, что есть mypy, который не позволит запустить программу в случае ошибки, то есть грубо говоря ошибки будут на этапе компиляции а не в runtime
Для меня это загадка, почему людям это задание кажется интересным, а там где второе такое видео за вакансию 150к, где тоже халява, не интересным, тут 3к просмотров, там 50, тут нет превьюхи привлекательной, а там хоть какая-то яркая:)
1. Забудь про insert в лист) Если тебе нужно сделать инсерт, ты что-то делаешь не так, асимптотика вставки O(длина листа). Либо передалай алгоритм, чтобы инсерт тебе был не нужен, либо использую хештаблицы/линкед листы/деревья поиска, в общем то, что подходит для быстрой вставки в рандомный индекс.
2. Возможно, в задачке подразумевалось, что интервалы могут пересекаться, иначе задачка слишком простая выходит.
3. Можешь такие задачки засовывать в какой-нибудь класс, конструктор на входе берет лист, по методу free_intervals возвращает свободные интервалы. Мб кто-то оценит)
Я бы посортил вход по левой границе, прошел указателем по массиву и на лету сконструировал свободные интервалы. Крайние случаи: пересечение интервалом точки 00:00 и вложенность одного интервала в другой (если допускаются пересечения), их не сложно обработать.
Успехов!
вопрос по первому пункту. я не шарю но разве чтобы вставить элемент в какой то индекс в связном списке не нужно для начала пройтись по этому листу до определенного индекса?
@@pslups9086, да, нужно скопировать в новый массив то, что было до этого элемента, потом добавить элемент, скопировать то, что после элемента, итого получается используется О(n) по времени для обхода списка и O(1) для операции вставки нового
2-3 недели обучаюсь программированию. Чето пересечения и вложенности не могу придумать как обработать. Создал функцию на проверку пересечения для 2х списков - на выходе True/False. Понятно, что и при пересечении, и при вложенности надо возвращать одно и тоже (минимальный из первых элементов двух списков и максимальных из вторых элементов). Но как это сделать? Допустим, я начал проверять каждый с каждым (кроме себя и предыдущих). Первый список ни с кем не пересекся - я его добавляю в новый список. Второй пересекся с 3им - добавляю их объединение, а если 3ий потом пересечется с 4ым??? На выходе опять будут пересекающиеся интервалы... Ну, можно ещё раз функцией прогнать - а сколько раз? Рекурсию чтоль жахнуть с остановкой, когда итоговый список вернет сам себя? Вот пока писал комментарий придумал чето)) Сча попробую.
UPD. Еле-еле получилось, но работает правильно, только если сквозь 00-00 изначально проходит не больше одного промежутка.
@@RANETKA234 Уберем отрезки, пересекающие точку 00-00, потом обработаем их отдельно. Создадим массив пар (время события, тип события), где события бывают 2-ух типов: кто-то занял кабинет и кто-то перестал занимать кабинет. Отсортируем этот массив по возрастанию и пройдем по нему циклом: заведем переменную counter = 0, если встречаем событие кабинет занят, то counter++, если событие кабинет перестал быть занят, то counter--. В итоге кабинет занят только тогда, когда counter > 0. Если counter становится равным 0, то промежуток от текущей точки до предыдущей, когда counter был равен нулю - промежуток, где кабинет занят. Остается сохранить такие промежутки, можно прямо в этом же цикле. Из них уже можно просто получить промежутки, когда кабинет свободен. Отрезки, пересекающие 00-00 можно обработать все разом, пройдя по ним циклом и найдя минимальный левый и максимальный правый концы, тогда отрезки от максимального левого до 0 и от 0 до макисмального правого заняты. Асимптотика O(n logn), где n длина списка с промежутками.
Вообще решения такого типа называются "сканирующая прямая", можешь погуглить.
Интересное задание. Почему нет прсомотров и комментариев :(
А не лучше , чем в цикл в цикле интервалов перебирать, просто на основе листа [[a,b],..,[y,z]] создать лист [[0,a],[b,c],..,[x,y],[z,1440] в одном цикле путем последовательного присвоения, или это дольше работать будет?
Не знаю, может и лучше, пока не увидел код, не могу сказать:) Вообще, нет ничего страшного во вложенных for, потому что если мы знаем, что у нас маленький список, например, 5 элементов, и мы пройдемся по нему 2 раза - for for, то будет 25 итераций, а если список будет из 30-ти элементов и мы пройдёмся по нему 1 раз - один for, то итерацией все равно будет больше. На видео внутренний цикл проходит по 2 элементам)
А что за синтаксис такой? В def стрелка ->
Тайп хинты)
-> говорит о том, какого типа данные функция вернёт, в python это что-то вроде фейка, пока что, разве что расширение какое-нибудь для IDE будет подсвечивать некорректное использование типов. Также знаю, что есть mypy, который не позволит запустить программу в случае ошибки, то есть грубо говоря ошибки будут на этапе компиляции а не в runtime
Как будто бы халява, но интерсная)
Для меня это загадка, почему людям это задание кажется интересным, а там где второе такое видео за вакансию 150к, где тоже халява, не интересным, тут 3к просмотров, там 50, тут нет превьюхи привлекательной, а там хоть какая-то яркая:)