← К задачамОткрыть курс →
Максимум непересекающихся отрезков
Дан список отрезков intervals, каждый отрезок — пара [start, end] (start <= end). Два отрезка считаются непересекающимися, если конец одного не больше начала другого (касание в точке допустимо: [1, 3] и [3, 5] не пересекаются).
Реализуйте функцию max_non_overlapping(intervals), которая возвращает максимальное количество попарно непересекающихся отрезков, которые можно выбрать. Классическая жадность: сортируем по правому концу.
Формат входа: intervals — список пар [start, end] (возможно пустой).
Формат выхода: целое число — максимум непересекающихся отрезков.
Примеры:
max_non_overlapping([[1, 2], [2, 3], [3, 4]]) -> 3
max_non_overlapping([[1, 10], [2, 3], [4, 5]]) -> 2
max_non_overlapping([]) -> 0
📖 Теория по теме:Сортировка и жадные алгоритмы
Курс по теме
Пройдите курс «Python с нуля» — по шагам, с проверкой
8 уроков · ~14 ч · теория, упражнения и экзамен с бейджем
def max_non_overlapping(intervals):
# ваш код
pass
Здесь появится результат. Напиши решение слева и нажми «Проверить код».
Для запуска тестов необходима авторизация.