n разовых заказов. Заказ i занимает время от starts[i] до ends[i] и приносит pays[i].
Одновременно можно выполнять только один заказ. Если заказ заканчивается в момент x, следующий может начаться ровно в x.
Выберите набор заказов без пересечений по времени с наибольшей суммарной оплатой и верните эту сумму.starts=[1, 4, 2, 6], ends=[4, 6, 7, 9], pays=[30, 20, 60, 25] → 75
Цепочка 1–4, 4–6, 6–9 идёт без пересечений и даёт 30 + 20 + 25 = 75. Самый дорогой заказ 2–7 (60) пересекается со всеми остальными, поэтому с ним больше 60 не получить.
starts=[1, 1, 1], ends=[5, 3, 2], pays=[8, 9, 4] → 9
Все заказы начинаются в момент 1 и пересекаются, поэтому берём один — самый дорогой, за 9.
starts=[3, 5], ends=[5, 8], pays=[10, 12] → 22
Первый заканчивается в 5, второй в 5 же начинается — это не пересечение, берём оба: 22.
n = starts.length = ends.length = pays.length ≤ 5 · 10⁴starts[i] < ends[i] ≤ 10⁹pays[i] ≤ 10⁴starts=[1, 4, 2, 6], ends=[4, 6, 7, 9], pays=[30, 20, 60, 25]
75
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 84 теста на сервере, включая скрытые.