Problema
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 = 10Entrada:
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;Explicação
Os dois primeiros projetos juntos somam 9. O último vale 10 e conflita com ambos, então escolha apenas ele.
Entrada:
projects = [
[1, 2, 4],
[2, 3, 5]
]
Saída esperada:
expected = 5Entrada:
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;Explicação
Ambos ocupam o dia 2. Escolha apenas o segundo, com recompensa 5.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Este é um problema de escalonamento de intervalos ponderado com faixas de tempo que se sobrepõem.
Dica 2
Ordene os projetos pelo dia de término e combine cada projeto com o último anterior compatível.
Dica 3
Seja preciso com os conflitos: outro projeto que começa no dia de término ainda se sobrepõe.
Complexidade esperada
tempo O(n log n), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.