Gewichtete Aktivitätsauswahl mit teilweise Überlappungszeiten

Question

Nehmen wir an, wir haben n Zeitpläne. Jeder Zeitplan i hat ein Gewicht w (i), eine Vorbereitungszeit prep (i) und eine Ruhezeitruhe (i).

Die Vorbereitungszeit bedeutet, dass wir, wenn wir Zeitplan i wählen, keine Zeitpläne wählen müssen i - prep (i), i - prep (i) + 1 ... i - 1.

Ruhezeit bedeutet, dass, wenn wir shedule i wählen, sind wir nicht verpflichtet, shedules zu wählen i + 1, i + 2 ... i + Rest (i)

Unsere Aufgabe ist es entsprechende Zeitpläne zur Auswahl nach Die obigen Einschränkungen, um zu maximieren.

Hinweis: Für i = 1, ignorieren wir prep (i) .Wir gehen davon aus, dass wir bereits vorbereitet sind.Für i = n wh ignoriert Rest (i).

Einschränkung: Die Vorbereitungszeit eines Zeitplans kann sich mit der Ruhezeit eines anderen Zeitplans überschneiden. Um ein Beispiel zu geben, wenn wir Ruhe (5) = 2, prep (8) = 2 haben, können wir beide Zeitpläne wählen. rest (5) = 2 bedeutet, dass wir, wenn wir 5 wählen, 6 und 7 nicht wählen dürfen. Prep (8) = 2 bedeutet, dass wir, wenn wir 8 wählen, nicht 6 und 7 wählen dürfen. So können wir sowohl 5 als auch 8 wählen.

Was ist der am besten geeignete Algorithmus für diese Aufgabe?

Wenn es nicht für die Beschränkung wäre, könnten wir sagen, dass jeder Zeitplan die Startzeit i - prep (i) und die Endzeit i + rest (i) hat. Wir hätten ein gewichtetes Aktivitätsauswahlproblem, so dass wir mit einem Greedy-Algorithmus ein optimales O (nlogn) erhalten hätten. Aber die Beschränkung verdirbt meinen Plan.

Answer 1

Lassen Sie f(i) die optimale Antwort sein, so dass i -th Aktivität die letzte ist. Wir können von Aktivität j zu Aktivität i gehen, wenn j < prep(i) und j + rest(j) < i. Sagen Sie es anders, f(i) = (max of f(j) among all valid j such that j < prep(i) and j + rest(j) < i) + 1. Diese Formel führt zu einer einfachen O(N^2) Lösung.

Aber wir können es besser machen! Lassen Sie uns einen beständigen Segmentbaum für den maximalen Betrieb behalten (eine Version für jede Position im Array). Anfangs ist es mit Nullen gefüllt. Für eine feste i gehen wir die prep(i) - 1 Version und führen eine maximale Abfrage auf [0, i - 1] Bereich. Dann ist f(i) der Wert dieses Maximums plus eins. Danach aktualisieren wir den Baum (das heißt, erstellen Sie eine neue Version) in der Position i + rest(i) mit f(i). Das ist es.

Wir tun O(N) bekommen Maximum und aktualisieren Sie ein Element Abfragen zu einem persistenten Segmentbaum, so dass die Lösung O(N log N) Zeit und Raum, die ziemlich gut aussieht. Es scheint jedoch ziemlich kompliziert zu sein.

Jetzt werden wir die Persistenz los. Wir können einen "normalen" (dh nicht-persistenten Segmentbaum) behalten und den Wert in einer Position i mit f(i) aktualisieren, wenn wir j = i + rest(i) erreichen (indem wir beispielsweise einen Vektor von Elementen behalten, die an jeder Position hinzugefügt werden) . Wir müssen uns nicht mehr um die zweite Einschränkung kümmern. Somit ist f(i) das Maximum im Bereich [0, prep(i) - 1] plus eins. Nachdem wir f(i) gefunden haben, drücken wir in den zu addierenden Vektor für die i + rest(i) Position.

Es verwendet immer noch O(N log N) Zeit, aber die Raumkomplexität ist jetzt linear und wir brauchen keinen persistenten Segmentbaum mehr (in der Tat, jedes Update kann nur den Wert erhöhen und wir brauchen einen maximalen Wert für ein Präfix, also Wir können hier einen binären Indexbaum anstelle eines Segmentbaums verwenden).