Activity Selection Problem

Q: Wie hoch ist die Zeitkomplexität des Aktivitätsauswahlproblems?

Das Sortieren nach Endzeit benötigt O(n log n) , und der anschließende Greedy-Durchlauf hat eine Laufzeit von O(n) , daher ist das Sortieren ausschlaggebend. Sind die Aktivitäten bereits nach Endzeit sortiert, löst der Durchlauf allein das Problem in O(n) Zeit und benötigt O(1) zusätzlichen Speicherplatz.

LeichtGreedy Sortieren

+10

Aktivität i läuft von Zeitpunkt start[i] bis Zeitpunkt finish[i]. Eine Person führt jeweils eine Aktivität aus, und die nächste Aktivität muss strikt nach dem Ende der vorherigen beginnen: Eine Aktivität, die genau zu dem Zeitpunkt beginnt, zu dem eine andere endet, kann nicht auf sie folgen.

Gib die größtmögliche Anzahl an Aktivitäten zurück, die eine Person ausführen kann.

Funktion

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: die Startzeit jeder Aktivität
finishinteger-array: die Endzeit jeder Aktivität; finish[i] gehört zu start[i]
Gibt zurückinteger: die meisten Aktivitäten, die eine Person nacheinander ausführen kann

Einschränkungen

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Eine Aktivität kann zur selben Zeit beginnen und enden. Die Arrays sind nicht sortiert.

Beispiele

Eingabe: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Ausgabe: 4
Erklärung: Die Bereiche 10 bis 13, 14 bis 19, 21 bis 22 und 25 bis 30 ergeben 4. Fünf ist unmöglich: 10 bis 13 überschneidet sich mit 12 bis 16 und 21 bis 22 mit 20 bis 24.

Eingabe: start = [1, 5, 9]finish = [5, 9, 12]
Ausgabe: 2
Erklärung: Die Aktivität von 5 bis 9 beginnt genau zu dem Zeitpunkt, an dem die erste endet, daher kann sie nicht auf sie folgen. 1 bis 5 und dann 9 bis 12 funktioniert, also lautet die Antwort 2.

Eingabe: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Ausgabe: 3
Erklärung: Die Aktivität von 0 bis 100 überschneidet sich mit allen anderen. Lässt man sie weg, passen 2 bis 4, 5 bis 7 und 8 bis 10 nacheinander: 3.

Weiterführende Frage

Zwei Personen arbeiten jetzt parallel und erledigen jeweils eine Aktivität nach der anderen. Wie viele Aktivitäten können sie gemeinsam erledigen, und welche Person sollte welche übernehmen?

Lösung

Jede Teilmenge der Aktivitäten auszuprobieren, dauert exponentiell lange. Eine einzige Greedy-Regel löst das Problem stattdessen: Wähle unter den Aktivitäten, die noch passen, immer diejenige, die zuerst endet. Durch das Sortieren nach Endzeit lässt sich diese Regel in einem einzigen Durchlauf umsetzen.

Wähle immer wieder den frühesten Endzeitpunkt

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Die Aktivität, die am frühesten endet, ist mindestens genauso gute Wahl für den ersten Schritt wie jede andere. Sie gibt dich nicht später frei, sodass alles, was auf eine andere erste Wahl folgen könnte, auch auf sie folgen kann, und durch den Austausch bleibt die Anzahl gleich. Nach dieser Wahl wiederholt sich das Problem mit den Aktivitäten, die beginnen, nachdem sie endet.

Im ersten Beispiel wählst du 10 bis 13, dann 14 bis 19, dann 21 bis 22 und schließlich 25 bis 30: vier.

Bei jeder Wahl werden alle n Aktivitäten durchlaufen, daher betragen die Kosten n mal die Antwort. Wenn alle 5000 Aktivitäten eine nach der anderen passen, sind das 25 Millionen Überprüfungen.

Algorithmus

Setze count = 0 und lastFinish = -1 unterhalb jedes Startzeitpunkts.
Durchsuche alle Aktivitäten nach derjenigen mit start[i] > lastFinish, die zuerst endet.
Wenn es keine gibt, gib count zurück.
Andernfalls erhöhe count um 1, setze lastFinish auf das Ende dieser Aktivität und durchsuche erneut.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Nach Endzeit sortieren und gierig auswählen

Idee

Sortiere einmal nach Endzeit, und du triffst auf die Aktivitäten in der Reihenfolge, in der die obigen Durchläufe sie durchsucht haben. Gehe die sortierte Liste durch und behalte dabei lastFinish, das Ende der letzten Aktivität, die du ausgewählt hast. Eine Aktivität mit start[i] > lastFinish ist die am frühesten endende, die noch passt, also wählst du sie aus. Jede andere überschneidet sich mit deiner letzten Auswahl, daher kostet es nichts, sie zu überspringen.

Sortiert lautet das erste Beispiel: 10 bis 13, 12 bis 16, 14 bis 19, 21 bis 22, 20 bis 24, 25 bis 30. Du wählst die erste, dritte, vierte und sechste aus: 12 liegt nicht nach 13, und 20 liegt nicht nach 22.

Bei gleichen Endzeiten ist keine Regel nötig. Sobald du eine Aktivität auswählst, die bei t endet, beginnt jede andere Aktivität, die ebenfalls bei t endet, bei oder vor t und wird übersprungen.

Algorithmus

Sortiere die Aktivitäten nach finish und verschiebe jeden Start zusammen mit seinem Finish.
Setze count = 0 und lastFinish = -1.
Gehe die Aktivitäten in dieser Reihenfolge durch. Wenn start[i] > lastFinish, addiere 1 zu count und setze lastFinish = finish[i].
Gib count zurück.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Stolperfallen und Grenzfälle

Sortieren nach Startzeit. Im dritten Beispiel beginnt 0 bis 100 zuerst und blockiert die anderen drei.
Zuerst die kürzeste Aktivität auswählen. Bei 1 bis 5, 5 bis 6 und 6 bis 10 ist 5 bis 6 die kürzeste und überschneidet sich mit den beiden anderen; 1 bis 5 und 6 bis 10 ergeben 2.
Mit ≥ statt > vergleichen. Im zweiten Beispiel ergibt das 3 statt 2.
finish allein sortieren. Jeder Start muss mit seinem eigenen Ende verschoben werden, sonst werden Starts den falschen Aktivitäten zugeordnet.
lastFinish bei 0 beginnen lassen. Eine einzelne Aktivität von 0 bis 1 wird dann übersprungen, weil 0 > 0 falsch ist.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Aktivitätsauswahlproblems?

Das Sortieren nach Endzeit benötigt O(n log n), und der anschließende Greedy-Durchlauf hat eine Laufzeit von O(n), daher ist das Sortieren ausschlaggebend. Sind die Aktivitäten bereits nach Endzeit sortiert, löst der Durchlauf allein das Problem in O(n) Zeit und benötigt O(1) zusätzlichen Speicherplatz.

Was ist das Problem mit N Besprechungen in einem Raum?

Es ist dasselbe Problem, dargestellt anhand von Besprechungen: ein Raum, N Besprechungen, und eine Besprechung kann erst beginnen, nachdem die vorherige beendet wurde. Sortiere die Besprechungen nach ihrer Endzeit und wähle jede aus, die beginnt, nachdem die zuletzt ausgewählte beendet wurde. Um die Besprechungen aufzulisten, notiere jeden Index, den du auswählst; bei gleicher Endzeit entscheidet der kleinere Index.

Ist das Aktivitätsauswahlproblem dynamische Programmierung?

Das ist möglich, aber nicht nötig. Eine Tabelle über die Aktivitäten, sortiert nach Endzeit, die für jede Aktivität die maximale Anzahl der Aktivitäten enthält, die mit ihr enden, liefert die Antwort in O(n²). Die gierige Wahl ist immer sicher, daher genügt ein einziger Durchlauf. Die Tabelle ist das richtige Werkzeug, wenn Aktivitäten Werte haben und du deren Summe maximierst.

def maxActivities(start, finish):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Erwartete Ausgabe