MP-Forum: maximale Intervalle bestimmen (Matroids Matheplanet)

Der besseren Übersicht wegen sind die Intervalle aus I nach oben geschoben worden.

Im Intervall [\alpha, \beta]_1 befinden sich 6 Intervall aus I, folglich gilt die Bedingung.

Im Intervall [\alpha, \beta]_2 befinden sich 4 Intervall aus I, folglich gilt auch hier die Bedingung. Schiebt man nun aber dieses Intervall um 1 nach rechts, so befinden sich nur noch 2 Intervalle aus I darin und die Bedingung ist verletzt, sodass das erste maximale Intervall nur bis 25 reicht.

Ich habe zwar schon eine Lösung, aber weil diese sehr naive ist, suche ich eine Verbesserung dazu:

Bisherige Methode:
1) Schiebe ein Suchintervalls [e-l,e] der Länge l von A nach B.
2) Falls die obige Bedingung erfüllt ist, merke dir die linke Position des Suchintervall (linker Startpunkt des Gültigkeitsbereiches, genannt s)
3) Falls die Bedingung nicht mehr erfüllt ist und man sich in einem Gültigkeitsbereich befindet, dann bildet das Intervall [s,e-1] ein maximales Intervall der gesuchten Form.
4) Mache bei 1) weiter

Verbesserungsmöglichkeiten sehe ich darin, dass ich, statt das Suchintervall [e-l,e] um 1 nach rechts zu schieben, nur die Anfangs- und Endpunkte betrachte, doch leider kam ich damit nicht so weit. Hat jemand eine Idee oder kennt Literatur, die sich damit beschäftigt?

LG Johannes

1. Erstelle eine Liste 'NEXT' 2. Sortiere NEXT 3. Gehe NEXT durch: counter <- 0 s <- -1 // Startpunkt eines maximalen Intervalls; falls s == -1, so liegt ein solches nicht vor while (NEXT nicht leer) do e <- NEXT.pop() x <- e.val if (e.type == AP) then counter++ else counter-- // falls es mehrere Eintraege mit dem Wert x gibt... while (NEXT.top().val == x) do n <- NEXT.pop() if (n.type == AP) then counter++ else counter-- if (counter >= m) then if ([x, x + l] in [A, B] && s == -1) then s <- x // neuer Startpunkt fuer ein maximales Intervall gefunden else if ( s \neq -1 ) then if ([s, x -1 + l] in [A, B]) then [s, x -1 + l] ist ein maximales Intervall else if (B - s >= l) then [s, B] ist ein maximales Intervall s <- -1

1. Erstelle eine Liste 'NEXT' 2. Sortiere NEXT 3. Gehe NEXT durch: counter <- 0 s <- -1 // Startpunkt eines maximalen Intervalls; falls s == -1, so liegt ein solches nicht vor while (NEXT nicht leer) do e <- NEXT.pop() x <- e.val if (e.type == AP) then counter++ else counter-- fi // falls es mehrere Eintraege mit dem Wert x gibt... while (NEXT.top().val == x) do n <- NEXT.pop() if (n.type == AP) then counter++ else counter-- od if (counter >= m) then if (x in [A-l+1, A-1]) s <- A else if ([x, x + l] in [A, B] && s == -1) then s <- x // neuer Startpunkt fuer ein maximales Intervall gefunden fi fi else if ( s \neq -1 ) then if ([s, x -1 + l] in [A, B]) then [s, x -1 + l] ist ein maximales Intervall else if (B - s >= l) then [s, B] ist ein maximales Intervall fi fi fi s <- -1 fi od