Berührende Segmente

Question

Kann mir bitte jemand Algorithmus vorschlagen.

Sie erhalten Anfangs- und Endpunkte von N Segmenten über die X-Achse. Wie viele dieser Segmente können auch an ihren Rändern von genau zwei Linien senkrecht zu ihnen berührt werden?

Probe Input:

3 
5 
2 3 
1 3 
1 5 
3 4 
4 5 
5 
1 2 
1 3 
2 3 
1 4 
1 5 
3 
1 2 
3 4 
5 6 

Beispielausgabe:

Case 1: 5 
Case 2: 5 
Case 3: 2 

Erläuterung:

• Fall 1: Es werden zwei Linien (parallel zur Y-Achse) crossing X- zeichnen Achse an Punkt 2 und 4. Diese beiden Linien berühren alle fünf Segmente.
• Fall 2: Wir können alle Punkte auch mit einer Linie berühren, die die X-Achse bei 2 schneidet.
• Fall 3: In diesem Fall ist es nicht möglich, mehr als zwei Punkte zu berühren.

Constraints:

1 ≤ N ≤ 10^5 
0 ≤ a < b ≤ 10^9 

Answer 1

Nehmen wir an, dass wir eine Datenstruktur haben, die effizient die folgenden Operationen unterstützt:

1. ein Segment hinzufügen.

2. Löschen eines Segments.

3. Gibt die maximale Anzahl der Segmente zurück, die einen Punkt abdecken (dh der "beste" Punkt).

Wenn eine solche Struktur haben, können wir das ursprüngliche Problem effizient auf die folgende Weise verwenden erhalten:

1. Lassen Sie uns eine Reihe von Ereignissen erstellen (ein Ereignis für den Beginn jedes Segments und ein für das Ende) und nach der x-Koordinate sortieren.

2. Fügen Sie der magischen Datenstruktur alle Segmente hinzu.

3. Iterieren Sie alle Ereignisse und gehen Sie folgendermaßen vor: Wenn ein Segment beginnt, fügen Sie eins zur Anzahl der aktuell abgedeckten Segmente hinzu und entfernen Sie es aus dieser Datenstruktur. Wenn ein Segment endet, subtrahiere eins von der Anzahl des aktuell abgedeckten Segments und füge dieses Segment der magischen Datenstruktur hinzu. Aktualisieren Sie nach jedem Ereignis die Antwort mit dem Wert der Anzahl der aktuell abgedeckten Segmente (es wird angezeigt, wie viele Segmente von dem Punkt abgedeckt werden, der dem aktuellen Ereignis entspricht) plus dem von der oben beschriebenen Datenstruktur zurückgegebenen Maximum (es zeigt, wie wir kann einen anderen Punkt auf die bestmögliche Weise wählen).

Wenn diese Datenstruktur alle angegebenen Operationen in O(log n) durchführen kann, dann haben wir eine O(n log n) Lösung (wir die Ereignisse sortieren und zu einem Durchgang über die sortierten Array machen eine konstante Anzahl von Abfragen an diese Datenstruktur für jede Herstellung Veranstaltung).

Wie können wir diese Datenstruktur implementieren? Nun, ein Segmentbaum funktioniert hier gut. Durch das Hinzufügen eines Segments wird ein Segment zu einem bestimmten Bereich hinzugefügt. Durch das Entfernen eines Segments wird eins von allen Elementen in einem bestimmten Bereich subtrahiert. Das Maximum ist nur eine Standardmaximaloperation in einem Segmentbaum. Daher benötigen wir einen Segmentbaum, der zwei Operationen unterstützt: Fügen Sie eine Konstante zu einem Bereich hinzu und erhalten Sie den Maximalwert für die gesamte Struktur. Es kann in O(log n) Zeit pro Abfrage durchgeführt werden.

Noch ein Hinweis: Ein Standard-Segmentbaum erfordert Koordinaten klein sein. Wir können davon ausgehen, dass sie niemals 2 * n überschreiten (wenn dies nicht der Fall ist, können wir sie komprimieren).

Answer 2

Eine O(N*max(logN, M)) Lösung, wobei M die mittlere Segmentgröße ist, in Common Lisp implementiert: touching-segments.lisp.

Die Idee besteht darin, zuerst an jedem interessanten Punkt die Anzahl der Segmente zu berechnen, die von einer Linie berührt werden würden (open-left-to-right im Lisp-Code). Kosten: O (NlogN)

Dann von rechts nach links berechnet sie, wieder an jedem interessanten Punkt P, der beste Ort für ein Liniensegment unter Berücksichtigung ganz nach rechts von P (open-right-to-left auf dem Lisp-Code). Kosten O (N * max (logN, M))

Dann ist es nur eine Frage der Suche nach dem Punkt, wo die Summe beider Werte an der Spitze liegt. Kosten O (N).

Der Code ist kaum getestet und enthält möglicherweise Fehler. Außerdem habe ich mich nicht darum gekümmert, Kantenfälle zu behandeln, wenn die Anzahl der Segmente Null ist.

Answer 3

1. Das Problem kann in O (Nlog (N)) Zeit pro Testfall gelöst werden.

2. beobachten, dass es eine optimale Platzierung von zwei vertikalen Linien ist, von denen jeder gehen durch einige Segmentendpunkte

3. Koordinaten Komprimiert Segmente. Weitere Informationen unter Was ist coordinate compression?

4. Erstellen eines sortierten Satz von Segmentendpunkte X

5. Sort Segmente [a_i, b_i] von a_i

6. Lassen Q a priority queue sein, die richtigen Endpunkte der Segmente speichert soweit bearbeitet

7. Sei T ein Max-Intervall-Baum, der über X-Koordinaten aufgebaut ist. Einige nützliche Lektüre bei What are some sources (books, etc.) from where I can learn about Interval, Segment, Range trees?

8. Für jedes Segment machen [a_i, b_i] -range Inkrementum-1 Abfrage bis T. Es ermöglicht einig x in abdecke maximale Anzahl von Segmenten zu finden [a, b]

9. Iterieren über die Elemente x von X für jede X Prozesssegmente (nicht bereits verarbeitet) mit x> = a_i. Die Verarbeitung umfasst das Drücken von b_i auf Q und das Durchführen einer [a_i, b_i] -Anweisung inkrementellen Abfrage um - (- 1) an T. Nach dem Entfernen von Q alle Elemente < x, A = Q.size ist gleich der Anzahl der Segmente, die x abdecken. B = T.rq (x + 1, M) gibt die maximale Anzahl der Segmente zurück, die x nicht abdecken und einige feste y> x abdecken. A + B ist ein Kandidat für eine Antwort.

Quelle: http://www.quora.com/What-are-the-intended-solutions-for-the-Touching-segments-and-the-Smallest-String-and-Regex-problems-from-the-Cisco-Software-Challenge-held-on-Hackerrank