Suchen Sie einen Punkt, der von maximalen Segmenten geteilt wird

Gegeben: $N$Segmente (Arrays) von geordneten ganzen Zahlen, ganze Zahlen könnten von bis .$-K$$K$

Beispiel:

Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

Sie können sie als [min, max] darstellen --- es ist äquivalent:

Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

Wie finde ich eine Ganzzahl, die zur maximalen Anzahl von Segmenten gehört? Für das gegebene Beispiel ist es 1.

Ich suche den effizientesten Algorithmus.

Verwenden wir , um den Anfang eines Segments zu bezeichnen, und , um das Ende zu bezeichnen. Erstellen Sie für jedes Segment zwei Paare, eines für jeden Endpunkt:$+$$-$

Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

Sortieren Sie die $2N$Paare nach ihrer ersten Koordinate (bei Gleichheit + vor - setzen). Sie können dies rechtzeitig tun$O(N \log N)$ mit jedem vernünftigen Sortieralgorithmus oder rechtzeitig $O(N + K)$Verwenden der schlüsselindizierten Zählung . Im Beispiel erhalten wir:

(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

Verarbeiten Sie nun die Endpunkte der Reihe nach. Behalten Sie die Anzahl der aktiven Segmente bei, die anfänglich 0 ist. Jedes Mal, wenn Sie a verarbeiten$+$Erhöhen Sie die Anzahl um 1. Jedes Mal, wenn Sie a verarbeiten $-$Verringern Sie die Anzahl um 1. Überprüfen Sie nach der Verarbeitung jedes Endpunkts, ob die neue Anzahl höher ist als die bisher größte Anzahl. Wenn dies der Fall ist, aktualisieren Sie Ihre Lösung.

(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1

Diese zweite Phase des Algorithmus dauert zeitproportional $N$. Der gesamte Algorithmus braucht Zeit$O(N \log N)$ mit einer generischen Sorte oder $O(N + K)$ mit schlüsselindizierter Zählung.

Erstellen wir ein Array der Größe 2 * k + 1, das alle mit 0 initialisiert ist. Für jedes Segment der Form [L, R] addieren wir 1 zum L- ^ten Index und subtrahieren 1 vom R + 1- ^ten Index.

Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.

Um das Ergebnis zu erhalten, führen wir eine Präfixsumme durch.

array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)

Sei ich der Index mit dem Maximalwert. Dann lautet die Antwort iK .
Lösen wir das gestellte Beispiel:

Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into 
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.

Die zeitliche Komplexität des obigen Ansatzes beträgt O (max (N, K)) .