Welchen Algorithmus für dieses Problem verwenden?

Question

Ich wurde kürzlich mit einem HackerRank-Interview-Test konfrontiert, wo ich das folgende Problem nicht richtig lösen konnte. Ich möchte nicht das genaue Problem für Privacy-Zwecke nennen, aber ich kann sagen, dass es mit diesem Namen in Google in Google war.

problem

Wir möchten ein Ereignis mit möglichst vielen Performer organisieren. Wir erhalten eine Liste möglicher Ankunftszeiten und Leistungsdauer von Performer-Ankunftszeiten. Unsere Funktion sollte die maximale Anzahl von Darsteller zurücksenden, die ohne Konflikte ausgewählt werden können.

Beispiel

n= 5
Ankünfte= [1, 3, 3, 5, 7] (Darsteller kommen in diesen Zeiten an)
Dauer= [2, 2, 1, 2, 1] (die Zeit, die zum Beenden ihrer Leistungen erforderlich ist)
Lösung= 4

Zum Zeitpunkt 1 können wir den Performer akzeptieren und zum Zeitpunkt 3. Zum Zeitpunkt 3 haben wir zwei widersprüchliche Auswahlmöglichkeiten und spielt keine Rolle, welche wir ausgewählt haben. Zeit 5 und 7 sind auch nicht in Konflikt.

meine Lösung

.
1. machte Tupeln der Ankünfte und Dauer durch Zippen. Sortierte die Tupel zuerst bei der Ankunft, dann auf Dauer.
2. äußerer für Zyklus, den ich von Anfang bis Ende beginnt. Initialisieren Sie neues Set in jedem ITER.
3. innerer Zyklus für J von I bis Ende. Prüfen Sie, ob j dem Satz ohne Konflikt hinzugefügt werden kann. Wenn ein Set länger ist als Max, den ich sparen kann.

Python-Quelle

Fragen

.
1. Gibt es bessere Möglichkeiten, Standardalgorithmen, um dieses Problem zu lösen?
2. Ich weiß, dass es einige Randkoffer gibt, für die mein Algorithmus nicht funktioniert. HackerRank hat meinen Algo bewertet, und es bestand nur 7/13 Testfälle. Was könnten einige Edge-Fälle sein, die ich vermisse?
3. ist das ein Suchproblem oder ein Optimierungsproblem?

Answer 1

Dies ist ein einfaches Intervallplanung Maximierung Problem, das in << EM> o (n log (n)) Zeit über einen einfachen gierigen Algorithmus. Der Trick besteht darin, Leistungen gemäß Endzeit und nicht startzeit zu sortieren.

Hier ist die Beschreibung der auf der Wikipedia-Seite, die ich verlinkt habe:

---

Mehrere Algorithmen, die auf den ersten Blick vielversprechend aussehen, eigentlich nicht die optimale Lösung finden:

• Auswählen der Intervalle, die frühest beginnen, ist keine optimale Lösung, denn wenn das früheste Intervall sehr lang ist, und akzeptiert, dass es uns angenommen wird, viele andere kürzere Anfragen abzulehnen.

• Auswählen der kürzesten Intervalle oder Auswahlintervalle mit den wenigsten Konflikten ist ebenfalls nicht optimal.

gierige Polynomösung

Der folgende gierige Algorithmus findet die optimale Lösung:

generasacodicetagpre.

Wenn wir in Schritt 1 ein Intervall auswählen, müssen wir möglicherweise viele Intervalle in Schritt 2 entfernen. Alle diese Intervalle überqueren jedoch zwangsläufig die Endzeit von X, und somit kreuzen sie alle einander. Daher können höchstens 1 dieser Intervalle in der optimalen Lösung sein. Daher gibt es für jedes Intervall in der optimalen Lösung ein Intervall in der gierigen Lösung. Dies beweist, dass der gierige Algorithmus tatsächlich eine optimale Lösung findet.

Eine formellere Erklärung wird von einem aufgeladenes Argument .

Der gierige Algorithmus kann in der Zeit o (n log n) ausgeführt werden, wobei n die Anzahl der Aufgaben ist, wobei ein Vorverarbeitungsschritt verwendet wird, in dem die Aufgaben sortiert sind durch ihre Endzeiten.

---

Answer 2

ansehen Maximale Intervallplanung .

Weisen Sie ein Intervall $ (S_I, T_I) $ zu jedem Performer, für $ i= 1, \ Punkte, N $ , was bedeutet, dass die Leistung zum Zeitpunkt $ s_i $ beginnt, und hat eine Dauer von $ T_I - S_I $ .

Nehmen Sie an, dass alle Intervalle nach ihrer Endzeit sortiert sind. Nur um Einfachheit halber davon auszugehen, dass alle Zeiten unterschiedlich sind (diese Annahme ist unnötig). Ihr Problem kann dann in $ O (n) $ Time gelöst werden.

Betrachten Sie $ (S_1, T_1) $ und lassen Sie $ i $ die Set von Intervallen schneiden Sie es (ohne $ (S_1, T_1) $ selbst).

ist leicht zu sehen, dass alle Intervalle in $ i $ vor $ t_1 $ ( Da sonst sie nicht kreuzen würden $ (S_1, T_1) $ ) und enden nach $ t_1 $ ( Andernfalls wäre $ t_1 $ nicht die minimale Endzeit). Dies bedeutet, dass alle Intervalle in $ i \ cup \ {(s_1, t_1) \ {{s_1, t_1) \} $ miteinander schneiden, und daher kann jede Lösung höchstens eines von ihnen enthalten.

lass $ s $ Sei eine Lösung (d. H. Eine Teilmenge von paarweise nicht kreuzenden Intervallen). Es ist immer möglich, $ S $ in eine neue Lösung $ s '$ , die $ (S_1, T_1) $ und so, dass $ | S '| \ ge | s | $ .

Wenn $ s \ cap i=emesyetet $ dann sind wir trivial fertig, da wir $ s '= auswählen können S \ cup \ {(s_1, t_1) \} $ (beachten Sie, dass dies auch den Fall enthält, in dem $ (S_1, T_1) \ in S $ ).

wenn $ s \ cap i \ neq \ emesyetet $ , $ (s_i, t_i) $ Seien Sie das einzigartige Intervall in $ s \ cap i $ . Jedes Intervall $ (s_j, t_j) \ in s \ setminus \ {(s_i, t_i) \} $ muss entweder erfüllen> $ s_j> t_i> t_1 $ oder $ s_i> t_j> t_1 $ . Der letztere Fall ist eigentlich unmöglich, da er widersprechen würde, dass $ (S_I, T_I) \ in S $ . Mit anderen Worten, wenn wir $ (S_I, T_I) $ mit $ (S_1, T_1) $ ) Wir erhalten immer noch eine realisierbare Lösung. Deshalb wählen wir $ s '= s \ cup \ {(S_1, T_1) \ {SetMinus \ {(S_I, T_I) \} $ .

Die unterste Linie besteht darin, dass immer eine optimale Lösung vorhanden ist, die $ (S_1, T_1) $ enthält. Daher können Sie immer $ (S_1, T_1) $ in Ihre Lösung hinzufügen, alle Intervalle in $ S \ Cup \ {löschen (S_1, T_1) \} $ und suchen Sie nach der optimalen Lösung zwischen den verbleibenden Intervallen. Dies beträgt den Ausführen des gierigen Algorithmus, der die Intervalle in der Reihenfolge betrachtet, und fügt ein beliebiges Intervall hinzu, das passt.

Aus Ihrer Instanz scheint es, dass die Startzeiten bereits sortiert sind. In diesem Fall können Sie den Trick von "Umkehrzeit umkehren", dh die Start- und Endzeiten, beispielsweise durch Ändern von $ (S_I, T_I) $ in $ (- T_I, -S_I) $ , mit dem Sie einen $ o (n) $ erhalten können -Mime-Algorithmus durch Überspringen des anfänglichen Sortierschritts, der bereits erforderlich ist, wodurch $ \ omega (n \ log n) $ Time erforderlich wäre.