Maximale Projektbelohnungen

Jedes Projekt ist ein Tupel [start_day, end_day, reward]. Es belegt jeden Tag von start_day bis end_day, einschließlich beider Grenzen. Du kannst an einem Tag nur an einem Projekt teilnehmen. Wähle eine Teilmenge mit der höchsten Gesamtbelohnung aus. Ein Projekt, das am Endtag eines anderen Projekts beginnt, steht mit diesem im Konflikt.

Implementiere project_rewards(projects).

Eingabe

projects: Zeilen mit jeweils drei Ganzzahlen: Starttag, Endtag und Belohnung.

Ausgabe

Gib die maximal mögliche Gesamtbelohnung zurück; die ausgewählten Projekte müssen nicht zurückgegeben werden.

Einschränkungen

1 ≤ projects ≤ 200.000. 1 ≤ start_day ≤ end_day ≤ 1.000.000.000. Belohnungen sind positive Ganzzahlen, höchstens 1.000.000.000.

Beispiele

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

Erwartete Ausgabe:
expected = 10

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

Erwartete Ausgabe:
long long expected = 10;

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

Erwartete Ausgabe:
long expected = 10;

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

Erwartete Ausgabe:
expected = 5

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

Erwartete Ausgabe:
long long expected = 5;

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

Erwartete Ausgabe:
long expected = 5;

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

• Projects — 1140