mit vielen Intervallen [ai, bi], finde ein Intervall, das sich mit der größten Anzahl von Intervallen überschneidet

Benutze Intervallbäume: Ссылка .

Wenn Sie einen zentrierten Intervallbaum verwenden, ist die Komplexität O (nlogn + m), wobei m die Gesamtzahl der Schnittpunkte ist (worst case m = n ^ 2).

Nach der Antwort von PengOne mache ich eine einfache Implementierung, die zwei n-artige Arrays anstelle von 2n-Arrays verwendet.

Code

Wenn die Werte ai und bi keine kleinen ganzen Zahlen & lt; N können sie dann durch Sortieren der Indizes in der Liste aller unterschiedlichen ai- und bi-Werte reduziert werden.

Gegeben die Eingabe "list", die alle eindeutigen ai und bi enthält. Der sortierte Index befindet sich in C #:

int [] index = Enumerable.Range (0, Liste.Zahl) .OrderBy (i = & gt; Liste [i]). ToArray ();

Durch Invertierung dieser Permutation kann jedem ai und bi ein Wert von 0 bis N - 1 zugewiesen werden.

int [] Werte = invertPermutation (Index);

ai kann durch Werte [location_of_ai_in_List]

Nun, da das neue ai und bi hergestellt werden kann & lt; N gibt es einen netten Trick, um das maximale überlappende Intervall in O (N) zu finden, sowie einige andere Fragen können schnell beantwortet werden.

1. deklariert ein Array von N + 1 Elementen:

   int [] Summe = neu int [N + 1];

2. für jedes Intervall ausführen:

   sum [ai] ++;

   Summe [bi + 1] -;

// Die Gesamtkomplexität dieses Schrittes ist O (N), da wir jedes Intervall in O (1) verarbeiten.

3. Aggregat:

   für (int i = 1; i & lt; = N; i ++) {     Summe [i] + = Summe [i - 1]; }

// Dies ist ein O (N) Schritt.

4. finde den Ort k, wo sum [k] maximal ist.
5. Iteriere die neuen Intervalle [ai, bi] und finde die erste, die die Position k enthält (dh. ai & lt; = k & amp; & k; = bi).

Dieses Intervall [ai, bi] ist eine Lösung und die Häufigkeit, mit der es alle anderen Intervalle schneidet, ist "sum [k] - 1" (nicht für sich selbst verantwortlich).

Ein alternativer Ansatz für Intervallbäume, der geeignet sein kann, wenn ai, bi kleine ganze Zahlen sind (z. B. vielleicht 16-Bit-Zahlen), ist:

1. Machen Sie ein Array A mit N Werten, wobei N größer ist als max (bi)
2. Löschen Sie alle Werte im Array auf 0
3. Schleife über die Intervalle und verändere A [ai]: = A [ai] +1, A [bi + 1]: = A [bi + 1] -1
4. Setzen Sie x = 0
5. Schlingen Sie über die Array-Berechnung x: = x + A [j] und suchen Sie nach dem größten Wert von x

Der Wert von x bei der Iteration gibt die Anzahl der Intervalle an, die den Punkt j schneiden, so dass der größte Wert den Punkt ergibt, der die meisten Intervalle schneidet.

Dies dauert O (N + n) Zyklen, also ist es nur nützlich, wenn n & gt; N für Ihre Anwendung.

(Streng genommen beantwortet dies die Frage nicht, da sie den Punkt findet, der am meisten schneidet. Sie sollten jedoch in der Lage sein, diesen Ansatz zu erweitern, um das Intervall zu finden, das am meisten schneidet.)

Sie können es in n.

[kleinste ai, größte bi]

Also ..