Минимальный набор чисел для покрытия интервала
Hard
Дан список отрезков на прямой в виде пар
Одна точка может покрывать сразу несколько отрезков, если лежит в их пересечении.
[l, r] (включительно). Нужно выбрать минимальное число точек так, чтобы каждый отрезок содержал хотя бы одну выбранную точку.Одна точка может покрывать сразу несколько отрезков, если лежит в их пересечении.
Примеры:
Вход:
[[1, 3], [2, 5], [3, 6]]
Выход:
1
Объяснение: Отрезки [1,3], [2,5], [3,6]. Точка 3 принадлежит всем трём сразу — достаточно одной точки.
Вход:
[[1, 2], [2, 3], [3, 4]]
Выход:
2
Объяснение: Отрезки [1,2], [2,3], [3,4]. Одной общей точки для всех трёх нет: например, 2 покрывает первые два, но не [3,4]; 3 покрывает последние два, но не [1,2]. Нужны как минимум две точки (например, 2 и 4, или 2 и 3).
Вход:
[[1, 10], [2, 3], [4, 5]]
Выход:
2
Объяснение: Отрезки [1,10], [2,3], [4,5]. Малые отрезки [2,3] и [4,5] не пересекаются, поэтому одной точки на оба не хватит. Точки 3 и 5 покрывают оба малых отрезка, а [1,10] покрыт автоматически — ответ 2.
Ограничения:
0 <= n <= 10^5; -10^9 <= l <= r <= 10^9
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!