Ricompense Massime dei Progetti

Ogni progetto è rappresentato da [start_day, end_day, reward]. Occupa tutti i giorni da start_day a end_day, estremi inclusi. Puoi partecipare a un solo progetto per ciascun giorno. Scegli un sottoinsieme di progetti con la somma totale di ricompense più alta possibile. Un progetto che inizia nello stesso giorno in cui un altro termina è considerato in conflitto con esso.

Implementa project_rewards(projects).

Input

projects: Righe di tre interi: giorno di inizio, giorno di fine e ricompensa.

Output

Restituisci la somma massima delle ricompense; non è necessario restituire i progetti scelti.

Vincoli

1 ≤ projects ≤ 200.000. 1 ≤ start_day ≤ end_day ≤ 1.000.000.000. Le ricompense sono interi positivi al massimo pari a 1.000.000.000.

Esempi

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

Output atteso:
expected = 10

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

Output atteso:
long long expected = 10;

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

Output atteso:
long expected = 10;

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

Output atteso:
expected = 5

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

Output atteso:
long long expected = 5;

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

Output atteso:
long expected = 5;

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

• Projects — 1140