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