Минимум точек, покрывающих все интервалы

Интервалы Сложная

Дан массив интервалов intervals. Найдите минимальное количество точек, таких что каждый интервал содержит хотя бы одну из них (классическая жадная задача с сортировкой по концу).

Сигнатура функции

min_points_to_cover(intervals: list[list[int]]) -> int

Примеры

Вход	Ожидаемый результат
[[[10, 16], [2, 8], [1, 6], [7, 12]]]	2
[[[1, 2], [3, 4], [5, 6], [7, 8]]]	4
[[]]	0
[[[1, 5]]]	1
[[[1, 5], [2, 6], [3, 7]]]	1
[[[1, 2], [2, 3], [3, 4]]]	2
[[[1, 4], [2, 5], [10, 12]]]	2
[[[1, 3], [4, 6], [7, 9], [2, 5]]]	3
[[[1, 100]]]	1
[[[1, 2], [3, 5], [4, 8], [9, 10]]]	3

1решили

1пытались

100%успешность

Войдите, чтобы решить →