Сортировка интервалов по началу
Упорядочивайте события перед обработкой
«Сортировка интервалов по началу» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое интервал
Интервал — это всего лишь пара чисел: начало и конец, например [2, 5]. Большинство задач об интервалах работают со списком таких пар. 📏
Порядок упрощает задачу
Исходные интервалы могут поступать в любом порядке, из-за чего их сложно анализировать. Сначала выполните сортировку, и хаотичный набор превратится в аккуратный проход слева направо.
Сортируйте по началу
Обычно интервалы сортируют по значению начала. Теперь каждый интервал начинается не раньше предыдущего, поэтому можно один раз пройти по списку вперёд.
intervals.sort(key=lambda x: x[0])Кортежи сортируются естественно
Если хранить интервалы как кортежи, Python бесплатно сортирует их по первому элементу, а затем по второму. Здесь даже не нужна функция-ключ.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Почему сначала сортируют по началу
Сортировка по началу позволяет обрабатывать события в порядке времени. Следующий интервал может начаться только позже, и это главный инвариант прохода.
Одинаковые начала
Если два интервала имеют одинаковое начало, порядок определяет вторичный ключ. Сортировка по (start, end) ставит сначала более короткие интервалы, что часто помогает.
intervals.sort(key=lambda x: (x[0], x[1]))Иногда сортируют по концу
В некоторых задачах, например при планировании максимального числа событий, сортируют по концу. Выбирайте ключ в соответствии с тем, какие данные нужны Вашему проходу.
intervals.sort(key=lambda x: x[1])Стоимость сортировки
Сортировка занимает O(n log n) времени, что обычно недорого и чаще всего определяет сложность таких задач. Последующий проход занимает всего O(n).
Сохраняйте дополнительные данные
Если каждый интервал содержит идентификатор или вес, сортируйте всю запись, а не только границы. Ключ определяет порядок, а остальные данные перемещаются вместе с ним.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Сначала сортируйте, затем выполняйте проход
Почти каждый алгоритм для интервалов устроен так: сначала sort, затем выполните проход. Правильный порядок превращает объединение, подсчёт и планирование в простые циклы.
Простая мысленная модель
Представьте интервалы гостями, приходящими на вечеринку. Сортировка по началу выстраивает их по времени прихода, чтобы Вы могли встречать их по одному.
Быстрая проверка
Вы собираетесь объединить список интервалов.
Итоги
Интервал — это пара «начало–конец», а сортировка по началу превращает беспорядочный список в аккуратный проход. Сначала сортируйте, затем двигайтесь вперёд за O(n). 🚀
Часто задаваемые вопросы
Урок «Сортировка интервалов по началу» бесплатный?
Да — полный текст урока «Сортировка интервалов по началу» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Сортировка интервалов по началу»?
Упорядочивайте события перед обработкой Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Сортировка интервалов по началу»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка интервалов по началу
- Слияние пересекающихся интервалов
- Метод сканирующей прямой для максимального перекрытия
- Минимальное число удалений без перекрытий