Описание задачи
Даны задачи с интервалом времени [start, end) и нагрузкой load. Нужно найти
максимальную суммарную нагрузку и интервалы, когда она достигалась.
Логика
- Интервалы полуоткрытые:
10..30включает 10, но не включает 30. - Точки изменения нагрузки:
start(+load) иend(-load). - Сортируем все точки событий, проходим слева направо (Scanline) и обновляем текущую сумму.
Пример
Вход
10: 10..30
10: 100..200000
5: 80..90
10: 31..40
5: 75..85
Выход
Max load: 10
10..30
31..40
80..85
100..200000
В интервале 80..85 пересекаются задачи (80..90 load 5) и (75..85 load 5). Сумма = 10.