25. Планирование работ#

📝 Условие#

Каждая работа имеет начало, конец и прибыль. Выберите непересекающиеся работы с максимальной суммарной прибылью.

Совет

На LeetCode main не нужен: данные приходят аргументами метода класса Solution.
Формат ниже — для запуска у себя через cin / cout.

📥 Входные данные#

В первой строке число n (1 ≤ n ≤ 5·10⁴). Далее n строк start end profit (start < end). Работу, заканчивающуюся в момент X, можно совмещать с работой, начинающейся в X.

📤 Выходные данные#

Одно число — максимальная прибыль.

🧪 Тесты#

Тест 1#

Ввод:

4
1 3 50
2 4 10
3 5 40
3 6 70

Вывод:

120

Тест 2#

Ввод:

5
1 3 20
2 5 20
3 10 100
4 6 70
6 9 60

Вывод:

150

Тест 3#

Ввод:

3
1 2 5
1 3 6
1 4 4

Вывод:

6

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня