4118. Минимальное число точек, покрывающих отрезки
Medium
1 решил
Дан список отрезков на прямой: каждый отрезок — пара
Нужно выбрать минимальное число точек на прямой так, чтобы каждый отрезок содержал хотя бы одну выбранную точку. Одна точка может «закрыть» сразу несколько отрезков, если лежит в их пересечении.
Пустой список →
Интуиция: это та же идея, что «минимальное число стрел, чтобы лопнуть все воздушные шары» (отрезки = шары).
[l, r] (включительно, l ≤ r).Нужно выбрать минимальное число точек на прямой так, чтобы каждый отрезок содержал хотя бы одну выбранную точку. Одна точка может «закрыть» сразу несколько отрезков, если лежит в их пересечении.
Пустой список →
0.Интуиция: это та же идея, что «минимальное число стрел, чтобы лопнуть все воздушные шары» (отрезки = шары).
Примеры:
Вход:
[[1, 3], [2, 5], [3, 6]]
Выход:
1
Объяснение: Точка 3 лежит во всех трёх отрезках → достаточно одной.
Вход:
[[1, 2], [2, 3], [3, 4]]
Выход:
2
Объяснение: Общей точки для всех трёх нет. Например, 2 закрывает первые два, 4 — последний → минимум 2.
Вход:
[[1, 10], [2, 3], [4, 5]]
Выход:
2
Объяснение: [2,3] и [4,5] не пересекаются — одной точки на оба мало. Точки 3 и 5 дают ответ 2.
Ограничения:
0 <= intervals.length <= 10^5
-10^9 <= l <= r <= 10^9
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!