Максимальный вес непересекающихся отрезков
Динамическое программирование
Сложная
Дан список отрезков intervals, каждый - тройка [начало, конец, вес] (конец не включается, то есть отрезки [1,3] и [3,5] не пересекаются). Выберите подмножество попарно непересекающихся отрезков с максимальной суммой весов и верните эту сумму.
Отсортируйте по концу, для ДП по префиксу используйте бинарный поиск последнего отрезка, не конфликтующего с текущим.
Сигнатура функции
weighted_interval_scheduling(intervals: list[list[int]]) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[[1, 3, 5], [2, 5, 6], [4, 6, 5], [6, 7, 4], [5, 8, 11], [7, 9, 2]]] | 17 |
| [[[1, 2, 10]]] | 10 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →