Dieses Problem ist außerhalb von mysql in einer anderen Sprache viel besser gelöst. Mit anderen Worten, Sie haben eine Matrix von Plätzen, von denen einige belegt sind (grau):
und Sie möchten alle Rechtecke mit gegebenen Abmessungen finden , sagen wir 3x5. Sie können dies sehr effizient mit linearem O(n) in zwei Durchgängen tun Zeit Algorithmus (n ist die Anzahl der Plätze):
1) in einem ersten Durchgang , gehen Sie nach Spalten von unten nach oben vor und geben Sie für jeden Sitzplatz die Anzahl der bis zu diesem verfügbaren aufeinanderfolgenden Sitzplätze an:
wiederholen, bis:
2) in einem zweiten Durchgang , gehen Sie zeilenweise vor und suchen Sie nach mindestens 5 aufeinanderfolgenden Zahlen größer oder gleich 3:
so erhalten Sie schließlich:
was die Lösung ergibt:diese Zahlenfolgen (grüne Flächen) sind Oberkanten der 2 möglichen Rechtecke 3x5 freier Plätze.
Der Algorithmus könnte leicht erweitert werden, um z.B. Holen Sie sich alle Rechtecke mit maximaler Fläche. Oder es könnte verwendet werden, um beliebige kontinuierliche Bereiche (nicht nur rechteckig) mit N Sitzen zu finden – suchen Sie einfach während des zweiten Durchgangs nach einer fortlaufenden Folge von Zahlen, die sich zu mindestens N summieren.
