Максимальная сумма наград за проекты

Каждый проект задаётся как [start_day, end_day, reward]. Проект занимает все дни с start_day по end_day включительно. В один день можно участвовать только в одном проекте. Выберите подмножество проектов с максимальной суммарной наградой. Проект, начинающийся в день окончания другого проекта, конфликтует с ним.

Реализуйте функцию project_rewards(projects).

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

projects: строки из трёх целых чисел: день начала, день окончания и награда.

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

Верните максимальную суммарную награду; выбранные проекты возвращать не требуется.

Ограничения

1 ≤ projects ≤ 200 000. 1 ≤ start_day ≤ end_day ≤ 1 000 000 000. Награды — положительные целые числа не более 1 000 000 000.

Примеры

Ввод:
projects = [
    [1, 2, 4],
    [3, 4, 5],
    [2, 3, 10]
]

Ожидаемый вывод:
expected = 10

Ввод:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {3, 4, 5},
    {2, 3, 10}
};

Ожидаемый вывод:
long long expected = 10;

Ввод:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {3, 4, 5},
    new long[] {2, 3, 10}
};

Ожидаемый вывод:
long expected = 10;

Ввод:
projects = [
    [1, 2, 4],
    [2, 3, 5]
]

Ожидаемый вывод:
expected = 5

Ввод:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {2, 3, 5}
};

Ожидаемый вывод:
long long expected = 5;

Ввод:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 5}
};

Ожидаемый вывод:
long expected = 5;

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

• Projects — 1140