Problema
Each project is [start_day, end_day, reward]. It occupies every day from start_day through end_day, including both endpoints. You can participate in only one project on a day. Choose a subset with the largest total reward. A project starting on another project’s end day conflicts with it.
Implement project_rewards(projects).
Input
projects: Rows of three integers: start day, end day, and reward.
Output
Return the maximum total reward; the chosen projects need not be returned.
Restrições
1 ≤ projects ≤ 200,000. 1 ≤ start_day ≤ end_day ≤ 1,000,000,000. Rewards are positive integers at most 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
The first two projects earn 9 together. The last earns 10 and conflicts with both, so choose it alone.
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
Both occupy day 2. Choose only the second, with reward 5.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
This is a weighted interval scheduling problem with overlapping time ranges.
Dica 2
Sort projects by end day and combine each project with the latest compatible earlier one.
Dica 3
Be precise about conflicts: another project starting on an end day still overlaps.
Complexidade esperada
O(n log n) time, O(n) extra space
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.