Récompenses Maximales de Projets

Chaque projet est représenté par [start_day, end_day, reward]. Il occupe chaque jour de start_day à end_day, bornes incluses. Vous ne pouvez participer qu'à un seul projet par jour. Choisissez un sous-ensemble de projets dont la récompense totale est maximale. Un projet qui commence le même jour qu'un autre se termine est en conflit avec celui-ci.

Implémentez project_rewards(projects).

Entrée

projects : Lignes de trois entiers : jour de début, jour de fin et récompense.

Sortie

Retournez la récompense totale maximale ; il n'est pas nécessaire de retourner les projets choisis.

Contraintes

1 ≤ projects ≤ 200 000. 1 ≤ start_day ≤ end_day ≤ 1 000 000 000. Les récompenses sont des entiers positifs d'au plus 1 000 000 000.

Exemples

Entrée :
projects = [
    [1, 2, 4],
    [3, 4, 5],
    [2, 3, 10]
]

Sortie attendue :
expected = 10

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

Sortie attendue :
long long expected = 10;

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

Sortie attendue :
long expected = 10;

Entrée :
projects = [
    [1, 2, 4],
    [2, 3, 5]
]

Sortie attendue :
expected = 5

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

Sortie attendue :
long long expected = 5;

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

Sortie attendue :
long expected = 5;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• Projects — 1140