Job Sequencing Problem

+10

Du erhältst n Jobs als zwei Arrays: Job i bringt profit[i] ein, wenn er bis zum Zeitpunkt deadline[i] abgeschlossen ist. Jeder Job dauert eine Zeiteinheit, du führst jeweils einen Job aus, beginnend bei Zeitpunkt 0, und kannst beliebige Jobs auslassen. Ein Job mit Deadline 2 kann von 0 bis 1 oder von 1 bis 2 ausgeführt werden.

Gib den größtmöglichen Gesamtprofit zurück, den du erzielen kannst.

Funktion

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: der Zeitpunkt, bis zu dem jeder Auftrag abgeschlossen sein muss, von 1 bis n
profitinteger-array: was jeder Auftrag einbringt; profit[i] gehört zu deadline[i]
Gibt zurückinteger: der größtmögliche Gesamtgewinn aus Aufträgen, die alle fristgerecht abgeschlossen werden können

Einschränkungen

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, wobei n die Anzahl der Aufträge ist
1 ≤ profit[i] ≤ 10⁵
Die Arrays sind nicht sortiert. Mehrere Aufträge können dieselbe Frist oder denselben Gewinn haben.

Beispiele

Eingabe: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Ausgabe: 120
Erklärung: Nur einer der beiden Aufträge mit Deadline 1 passt, also führe den mit dem Wert 50 aus. Der Auftrag mit dem Wert 30 wird dann zu seiner Deadline 2 fertig und der Auftrag mit dem Wert 40 zu seiner Deadline 3: 50 + 30 + 40 = 120.

Eingabe: deadline = [1, 1, 1]profit = [5, 9, 7]
Ausgabe: 9
Erklärung: Alle drei Aufgaben müssen bis Zeitpunkt 1 abgeschlossen sein, und nur eine Aufgabe passt davor. Die beste davon bringt 9 ein.

Weiterführende Frage

Was ist, wenn Job i statt einer Zeiteinheit duration[i] Zeiteinheiten dauert? Ergibt es immer noch die beste Gesamtsumme, wenn man zuerst den profitabelsten Job erledigt?

Lösung

Du entscheidest, welche Aufträge du behältst und wann du sie ausführst. Eine gierige Regel legt beides fest: Nimm die Aufträge in absteigender Reihenfolge ihres Gewinns und plane jeden in den spätestmöglichen freien Zeitschlitz bis einschließlich seiner Frist ein. Gibt es keinen freien Zeitschlitz, überspringe den Auftrag. Eine disjunkte Mengenstruktur findet diesen Zeitschlitz, ohne bereits belegte Zeitschlitze zu durchlaufen.

Gierig nach Gewinn, Suche nach einem freien Zeitfenster

Idee

Teile die Zeit in Zeitschlitze ein: Zeitschlitz t läuft von t-1 bis t, ein Auftrag mit Frist d kann die Zeitschlitze 1 bis d nutzen, und keine Frist überschreitet n. Es ist sicher, zuerst den profitabelsten Auftrag zu nehmen: Wenn alle Zeitschlitze, die er nutzen könnte, belegt sind, bringt es mindestens genauso viel, ihn gegen den Auftrag in einem dieser Zeitschlitze auszutauschen. Es ist sicher, den spätestmöglichen Zeitschlitz zu belegen, denn frühe Zeitschlitze sind die einzigen, die Aufträge mit kurzen Fristen nutzen können.

Der Aufwand entsteht durch das Durchsuchen. Wenn jede Frist n beträgt, geht der k-te Auftrag an k-1 belegten Zeitschlitzen vorbei: etwa n²/2, also 12.5 Millionen Schritte bei n = 5000.

Algorithmus

Sortiere die Aufträge nach Gewinn, absteigend, und behalte jede Deadline zusammen mit ihrem Gewinn.
Erstelle ein Array taken mit n + 1 Flags, die alle auf false gesetzt sind.
Gehe für jeden Auftrag t von seiner Deadline rückwärts bis 1 durch und halte beim ersten nicht belegten Slot an.
Wenn du einen gefunden hast, markiere ihn als belegt und addiere den Gewinn des Auftrags zu total.
Gib total zurück.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Gierig nach Gewinn mit einer disjunkten Menge freier Zeitfenster

Idee

Der Scan durchläuft immer wieder dieselben belegten Slots. Eine disjunkte Mengenstruktur über die Slots 0 bis n überspringt sie: parent[t] = t, solange Slot t frei ist, und wird er belegt, setzt man parent[t] = t-1, sodass man beim Verfolgen der Zeiger von einer Frist aus beim letzten freien Slot landet. Slot 0 zu erreichen bedeutet, dass nichts mehr frei ist. Beim Path Halving zeigt jeder Slot, den du durchläufst, zwei Schritte weiter nach vorn, sodass spätere Durchläufe kürzer sind.

Im dritten Beispiel belegen die Jobs mit den Werten 60 und 50 die Slots 2 und 1. Der Job mit dem Wert 20 und der Frist 2 folgt der Kette 2 zu 1 zu 0 und wird übersprungen.

Das Sortieren kostet O(n log n), und mit Path Halving kostet jede Suche amortisiert O(log n), sodass die Gesamtlaufzeit bei O(n log n) bleibt.

Algorithmus

Sortiere die Aufträge nach Gewinn, beginnend mit dem höchsten, und behalte dabei jede Frist zusammen mit ihrem Gewinn.
Setze parent[t] = t für jeden Slot t von 0 bis n.
Beginne für jeden Auftrag bei slot = deadline und folge parent, bis parent[slot] == slot gilt. Halbiere dabei den Pfad.
Wenn slot > 0 gilt, addiere den Gewinn des Auftrags und setze parent[slot] = slot-1; andernfalls überspringe den Auftrag.
Gib die Gesamtsumme zurück.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Stolperfallen und Grenzfälle

Einen Job im frühesten freien Zeitfenster platzieren. Im dritten Beispiel würde der Job mit einem Wert von 60 Zeitfenster 1 belegen, und der Job mit einem Wert von 50 ginge verloren: 80 statt 110.
Jobs nach Deadline auswählen. Bei den Deadlines [1, 1] und den Gewinnen [1, 100] belegt der günstige Job das einzige Zeitfenster, und du erzielst 1 statt 100.
Das Zeitfenster-Array mit n statt n + 1 dimensionieren. Eine Deadline gleich n führt dann zu einem Zugriff über das Ende hinaus.
Die Gewinne für sich allein sortieren. Jede Deadline muss mit ihrem Gewinn verschoben werden.
Den Suchschritt rekursiv schreiben. Eine Kette über Tausende belegte Zeitfenster kann zu einem Stacküberlauf führen; verwende eine Schleife.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Job-Sequencing-Problems?

Mit einer disjunkten Mengenstruktur beträgt der Zeitaufwand O(n log n), der von der Sortierung dominiert wird, und der Speicherbedarf O(n). Das Rückwärtsdurchsuchen ab jeder Frist nach einem freien Platz kostet O(n²), wenn die meisten Fristen weit in der Zukunft liegen.

Warum funktioniert der gierige Ansatz bei der Auftragsplanung?

Ein bester Zeitplan enthält den profitabelsten Auftrag. Wird er ausgelassen und ist vor seiner Frist noch ein Zeitfenster frei, bringt seine Aufnahme mehr ein; sind alle solchen Zeitfenster belegt, bringt sein Austausch mindestens ebenso viel ein. Das Argument lässt sich für die verbleibenden Aufträge wiederholen.

Kann die Auftragsreihenfolge stattdessen mit einem Heap gelöst werden?

Ja. Sortiere die Aufträge nach Frist und füge jeden Gewinn in einen Min-Heap ein. Immer wenn der Heap mehr Aufträge enthält, als die aktuelle Frist zulässt, entferne den kleinsten Gewinn. Am Ende enthält der Heap die beste Auswahl an Aufträgen, und ihre Summe ist die Antwort, in O(n log n).

def jobSequencing(deadline, profit):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Erwartete Ausgabe