Problem
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 = 10Eingabe:
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;Erläuterung
Die ersten beiden Projekte bringen zusammen 9 ein. Das letzte bringt 10 ein und steht mit beiden im Konflikt, daher wähle es alleine.
Eingabe:
projects = [
[1, 2, 4],
[2, 3, 5]
]
Erwartete Ausgabe:
expected = 5Eingabe:
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;Erläuterung
Beide belegen Tag 2. Wähle nur das zweite Projekt mit einer Belohnung von 5.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Das ist ein Weighted-Interval-Scheduling-Problem mit überlappenden Zeitbereichen.
Hinweis 2
Sortiere Projekte nach ihrem Endtag und kombiniere jedes Projekt mit dem zuletzt kompatiblen früheren.
Hinweis 3
Sei genau bei Konflikten: Ein anderes Projekt, das an einem Endtag startet, überlappt noch.
Erwartete Komplexität
Zeit O(n log n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.