Wenn Sie Bücher stapeln, möchten Sie normalerweise die größten unten und die kleinsten oben platzieren. Bei meiner latenten Zwangsstörung fühle ich mich jedoch sehr unwohl, wenn ich zwei Bücher habe, von denen eines kürzer (in der Höhe), aber breiter als das andere ist. Egal in welcher Reihenfolge ich sie einlege, das obere Buch wird auf einer Seite über das untere Buch hinausragen.

Angenommen, ein Buch hat Dimensionen (10,15)und ein anderes hat Dimensionen (11,14). Egal in welche Richtung ich sie lege, ich bekomme einen Überhang. Wenn ich aber Bücher mit den Maßen (4,3)und habe (5,6), kann ich ein Überhängen vermeiden, indem ich das letztere unter das erstere lege.

Für die Zwecke dieser Herausforderung werden Überhänge nur in Bezug auf das Buch direkt unten betrachtet . Zum Beispiel , wenn ich einen Stapel haben (5,5), (3,3), (4,4)(nicht , dass jeder vernünftige Mensch würde das tun), die Top-Buch zählt als Überhang, obwohl es über den Boden Buch erstreckt sich nicht. In ähnlicher Weise der Stapel (3,3), (3,3), (4,4)hat auch nur einen Überhang, trotz des oben Buch über den Boden eines erstreckt.

Die Herausforderung

Sortieren Sie die Paare / Bücher anhand einer Liste von ganzzahligen Paaren für die Buchdimensionen so, dass die Anzahl der Überhänge minimal ist. Sie dürfen die Bücher nicht drehen - ich möchte, dass alle Buchrücken in die gleiche Richtung weisen. Wenn es mehrere Lösungen mit der gleichen Anzahl von Überhängen gibt, können Sie eine solche Reihenfolge wählen. Ihr Sortieralgorithmus muss nicht stabil sein. Bei Ihrer Implementierung wird möglicherweise davon ausgegangen, dass die Buchgröße jeweils weniger als 2 ¹⁶ beträgt.

Zeitkomplexität: Um dies etwas interessanter zu gestalten, muss die asymptotische Worst-Case-Komplexität Ihres Algorithmus in Bezug auf die Größe des Stapels polynomisch sein. Sie können also nicht alle möglichen Permutationen testen. Bitte fügen Sie einen kurzen Beweis für die Optimalität und Komplexität Ihres Algorithmus und optional ein Diagramm bei, das die Skalierung für große Zufallseingaben zeigt. Natürlich können Sie die maximale Größe der Eingabe nicht als Argument verwenden, dass Ihr Code in O (1) ausgeführt wird.

Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN, ARGV oder ein Funktionsargument in einem beliebigen (nicht vorverarbeiteten) Listenformat vornehmen und das Ergebnis entweder drucken oder zurückgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Ich bin zuversichtlich, dass es eine Polynomlösung gibt, aber wenn Sie mir das Gegenteil beweisen können, können Sie einen solchen Beweis anstelle einer Golf-Vorlage einreichen. In diesem Fall können Sie P ≠ NP annehmen . Ich werde den ersten korrekten solchen Beweis annehmen und ihm eine Prämie gewähren.

Beispiele

In:  [[1, 1], [10, 10], [4, 5], [7, 5], [7, 7], [10, 10], [9, 8], [7, 5], [7, 5], [3, 1]]
Out: [[10, 10], [10, 10], [9, 8], [7, 7], [7, 5], [7, 5], [7, 5], [4, 5], [3, 1], [1, 1]]

In:  [[4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [5, 4], [4, 5]]
Out: [[4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4]]
  or [[5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5]]

In:  [[2, 3], [1, 1], [5, 5], [7, 1]]
Out: [[5, 5], [2, 3], [7, 1], [1, 1]]
 or  [[5, 5], [2, 3], [1, 1], [7, 1]]
 or  [[7, 1], [5, 5], [2, 3], [1, 1]]
 or  [[7, 1], [1, 1], [5, 5], [2, 3]]

Ich habe diese von Hand erstellt. Lassen Sie mich wissen, wenn Sie Fehler entdecken.

Pyth , 30

FN_SQFbYIgeeYeb~b]NB)E~Y]]N;sY

Dies ist ein direkter Golf von Grcs fantastischem Algorithmus. Hier ist das genaue Äquivalent des obigen Pyth-Programms in seinem kompilierten Python-Code.

Q = eval(input())
Y = []
for N in sorted(Q)[::-1]:
     for b in Y:
         if Y[-1][-1] >= b[-1]:
             b += [N]
             break
     else:
         Y += [[N]]
print(Psum(Y))

In diesem Zusammenhang entspricht die Psum(Y)Funktion dem Python sum(Y,[]).

Tatsächlich kompilierter und ausgeführter Code (von pyth -d):

Y=[]
Q=copy(eval(input()))
for N in neg(Psorted(Q)):
 for b in Y:
  if gte(end(end(Y)),end(b)):
   b+=[N]
   break
 else:
  Y+=[[N]]
Pprint("\n",Psum(Y))

Python, 113

P=[]
for n in sorted(input())[::-1]:
 for p in P:
  if p[-1][1]>=n[1]:p+=[n];break
 else:P+=[[n]]
print sum(P,[])

Nach dem Sortieren der Bücherliste in absteigender Reihenfolge (zuerst nach Breite und dann nach Höhe) werden die Bücher in Stapel ohne Überlappungen unterteilt. Um zu bestimmen, wo jedes Buch abgelegt werden soll, wird seine Höhe mit der Höhe des obersten Buches in jedem Stapel verglichen. Es wird auf den ersten möglichen Stapel gelegt, oder es wird ein neuer Stapel erstellt.

Ich bin nicht sehr gut mit Zeitkomplexität, aber ich glaube, dass es den schlimmsten Fall von O ( N ² ) geben würde. Es gibt zwei Schleifen mit jeweils höchstens N Iterationen. Ich benutze auch Pythons eingebaute Sortierung, die O ( n log n ) ist.

Mein erster Beweis, dass dieser Algorithmus optimale Lösungen liefert, hat sich als falsch herausgestellt. Ein großes Dankeschön geht an @xnor und @ Sp3000 für die großartige Diskussion im Chat über den Beweis dessen (die Sie ab hier lesen können ). Nachdem @xnor einen korrekten Beweis erarbeitet hatte, stellte er fest, dass ein Teil davon bereits erledigt war ( Dilworth-Theorem ).

Hier ist ohnehin eine Übersicht über die Beweise (Dank an @xnor und @ Sp3000).

Zunächst definieren wir den Begriff eines Antipiles oder einer Antichain ( zitiert aus @xnor ):

Ein Antipile ist eine Folge von Büchern mit abnehmender Höhe, aber zunehmender Breite
. Jedes aufeinanderfolgende Buch ist also streng größer, aber streng weniger breit.
Beachten Sie, dass jedes Buch in einem Antipile über jedes andere Buch in einem Antipile
hinausragt in dem gleichen Stapel sein
Als Konsequenz , wenn Sie eine antipile von x Büchern finden können, dann müssen diese Bücher in verschiedenen Haufen sein
Also, die Größe der größten antipile von der Anzahl der Pfähle gebunden ein niedrigen

Dann sortieren wir die Bücher in absteigender Reihenfolge nach ihrer Breite (erste) und ihrer Höhe (zweite) *.

Für jedes Buch B gehen wir wie folgt vor:

1. Wenn B auf den ersten Stapel passt, legen wir ihn dort ab und ziehen weiter.
2. Ansonsten finden wir den frühesten * Stapel x, auf den B gelegt werden kann. Dies kann bei Bedarf ein neuer Stapel sein.
3. Als nächstes verknüpfen wir B mit P , wobei P das oberste Buch auf dem vorherigen Stapel x - 1 ist .
4. Wir wissen jetzt, dass:
   • B ist streng * kleiner als P , da die Bücher in absteigender Reihenfolge nach Breite sortiert sind
   • B ist streng größer als P , sonst hätten wir B über P gelegt

Jetzt haben wir von jedem Buch (außer denen im ersten Stapel) eine Verknüpfung zu einem Buch im vorherigen Stapel erstellt, das breiter und höher ist.

Das hervorragende Diagramm von @ Sp3000 verdeutlicht dies:

Wenn wir einem Pfad vom letzten Stapel (rechts) zum ersten Stapel (links) folgen, erhalten wir ein Antipile. Wichtig ist, dass die Länge dieses Antipiles der Anzahl der Pfähle entspricht. Daher ist die Anzahl der verwendeten Stapel minimal.

Da wir die Bücher in die minimale Anzahl Stapel ohne Überlappungen unterteilt haben, können wir sie übereinander stapeln, um einen Stapel mit der minimalen Anzahl Überlappungen zu erhalten.

_{* Dieser hilfreiche Kommentar erklärt einige Dinge}