Ctrl K

Самая длинная цепочка отрезков

Средняя
Дан список отрезков segments, где segments[i] = [start, end] и start < end. Отрезок [c, d] может идти в цепочке сразу после отрезка [a, b], если b < c — то есть следующий начинается строго после конца предыдущего. Верните длину самой длинной цепочки. Отрезки можно брать в любом порядке, использовать все не обязательно.
Пример 1
segments=[[1, 4], [5, 6], [2, 3], [4, 8]] → 2

Например, [2, 3] → [4, 8] или [2, 3] → [5, 6] — цепочки длины 2. Длиннее не выйдет: у [1, 4] и [4, 8] общий конец, а [5, 6] не начинается после 8.

Пример 2
segments=[[-3, -1], [10, 12], [0, 5]] → 3

Все три отрезка выстраиваются в цепочку: [-3, -1] → [0, 5] → [10, 12].

Пример 3
segments=[[0, 9], [1, 8], [2, 7]] → 1
Ограничения
  • 1 ≤ len(segments) ≤ 10⁵
  • -1000 ≤ start < end ≤ 1000
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОтменить как можно меньше встреч СредняяДобыча, которая делится на троих СредняяСамая сильная команда СредняяРазломать шоколадку СредняяНаибольшее число, кратное трём Сложная
загружаем Python…
Вход
segments=[[1, 4], [5, 6], [2, 3], [4, 8]]
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 101 тест на сервере, включая скрытые.