Recompensas Máximas de Projetos

Cada projeto é representado por [start_day, end_day, reward]. Ele ocupa todos os dias de start_day até end_day, incluindo ambos os extremos. Você só pode participar de um projeto por dia. Escolha um subconjunto com a maior soma de recompensas. Um projeto que começa no mesmo dia em que outro termina entra em conflito com ele.

Implemente project_rewards(projects).

Entrada

projects: Linhas com três inteiros: dia de início, dia de término e recompensa.

Saída

Retorne a maior soma possível de recompensas; não é necessário retornar os projetos escolhidos.

Restrições

1 ≤ projects ≤ 200.000. 1 ≤ start_day ≤ end_day ≤ 1.000.000.000. As recompensas são inteiros positivos de no máximo 1.000.000.000.

Exemplos

Entrada:
projects = [
    [1, 2, 4],
    [3, 4, 5],
    [2, 3, 10]
]

Saída esperada:
expected = 10

Entrada:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {3, 4, 5},
    {2, 3, 10}
};

Saída esperada:
long long expected = 10;

Entrada:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {3, 4, 5},
    new long[] {2, 3, 10}
};

Saída esperada:
long expected = 10;

Entrada:
projects = [
    [1, 2, 4],
    [2, 3, 5]
]

Saída esperada:
expected = 5

Entrada:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {2, 3, 5}
};

Saída esperada:
long long expected = 5;

Entrada:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 5}
};

Saída esperada:
long expected = 5;

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

• Projects — 1140