Interview Puzzle auf einem Liniensegment auf Reisen

Question

Hier ist eine interessante Frage, die ich kam auf:

Sagen wir einfach auf eine Reihe Linie Länge M, wo 0 < M <= 1,000,000,000, Sie N (1 < N <= 100,000) integer Punktpaare gegeben. In jedem Paar repräsentiert der erste Punkt, wo sich ein Objekt gerade befindet, und der zweite Punkt gibt an, wohin ein Objekt bewegt werden soll. (Denken Sie daran, second Punkt kann kleiner als die first sein).

Angenommen, Sie beginnen an der Stelle 0 und haben einen Wagen, der 1 Objekt enthalten kann. Sie möchten alle Objekte von ihren Anfangspositionen zu ihren jeweiligen Endpositionen bewegen, während Sie die kleinste Entfernung entlang der Nummernlinie (nicht Verschiebung) bewegen. Sie müssen am Punkt M enden.

Nun, ich habe versucht, dieses Problem zu einem einfacheren Problem zu reduzieren. Um ehrlich zu sein, kann ich nicht einmal an eine rohe Gewalt denken (möglicherweise gierige) Lösung. Mein erster Gedanke war jedoch, eine Rückwärtsbewegung in zwei Vorwärtsbewegungen zu degenerieren, aber das scheint nicht in allen Fällen zu funktionieren.

zog ich diese 3 Beispieltestfälle in

Die Antwort auf den ersten Testfall ist 12. Zuerst nehmen Sie die red Artikel bei Punkt 0. Dann bewegen Sie sich zum Punkt 6 (Abstand = 6), lassen Sie den Artikel red vorübergehend fallen, dann holen Sie sich den green Artikel. Dann bewegen Sie sich zu Punkt 5 (Abstand = 1) und lassen Sie den green Artikel fallen. Dann gehen Sie zurück zum Punkt 6 (Abstand = 1) und nehmen Sie den red Artikel, den Sie fallen gelassen haben, gehen Sie zu Punkt 9 (Abstand = 3), dann gehen Sie zum Punkt 10 (Abstand = 1), um die Sequenz zu beenden.

Die Gesamtstrecke war 6 + 1 + 1 + 3 + 1 = 12, was der minimal mögliche Abstand ist.

Die anderen beiden Fälle haben Antworten von 12, glaube ich. Ich kann jedoch keine allgemeine Regel finden, um es zu lösen.

Wer hat irgendwelche Ideen?

Answer 1

Kann sein, ich bin Missverständnis, das Problem aber was ist mit den folgenden:

1. sortieren die Paare durch die erste Zahl des Paares, die den aktuellen Standort
2. Verschieben entlang der Linie zu tauschen Elemente ist ihre richtige Stelle (Sie eine temporäre Variable)

die Tatsache, dass es garantiert sortiert ist, dass Sie nicht hin und her, die Elemente gehen, um sie an der richtigen Stelle zu platzieren (unabhängig wenn die Leitung als ein Array oder einer Liste dargestellt)

Update nach @templatetypedef Kommentar:
Verwenden a HashTable alle Paare zu speichern. Verwenden Sie die aktuelle Position jedes Paars als Indexschlüssel.
Verwenden Sie einen zweiten Index über die Paare.

1. Get next pair according to index from the line. 
2. If current pair exists in hashtable then place element to its target location. 
    2.a Remove pair from hashtable. 
    2.b Make current pair the target location. Then go to step 1 
ELSE 
     Increment current index until you get a pair present in the hashtable. Go to step 2 

Answer 2

Angenommen, Sie diese Schritte gegeben (a, b), (c, d), (e, f), ... dann der Mindestabstand Sie reisen müssen, ist abs(b - a) + abs(d - c) + abs(f - e) + ... und die tatsächliche Entfernung Sie ist abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ... reisen.
Bei einer Reihe von Verschiebungen ist der Punkt die Minimierung der Funktion "Verfahrweg", indem Elemente vertauscht werden. Wenn Sie eine bestimmte Kombination als Knoten betrachten und alle Kombinationen, die Sie daraus als Kanten erreichen können, können Sie einen der vielen Graph-Suchalgorithmen verwenden, die eine Heuristik verwenden. Ein Beispiel ist die beam search.

Answer 3

This is the asymmetric traveling salesman problem. Sie können sich das als Grafik vorstellen. Die Kanten sind jeweils (Anfang, Ende) Paar, eins für jedes (0, Start) und alle anderen Paare von (Ende, Start).

Nimmt man NP! = P an, hat es eine exponentiell erwartete Laufzeit.