← К задачам
Средне · +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
def max_non_overlapping(intervals):
    # ваш код
    pass
Для запуска тестов необходима авторизация.
Поддержать проект