← К задачам
Средне · +3Жадные алгоритмыСортировка

Максимум непересекающихся отрезков

Дан список отрезков 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
py
Курс по теме
Пройдите курс «Python с нуля» — по шагам, с проверкой
8 уроков · ~14 ч · теория, упражнения и экзамен с бейджем
Открыть курс →
def max_non_overlapping(intervals):
    # ваш код
    pass
Здесь появится результат. Напиши решение слева и нажми «Проверить код».
Для запуска тестов необходима авторизация.