Ce problème est bien mieux résolu en dehors de mysql, dans une autre langue. Autrement dit, vous avez une matrice de sièges dont certains sont occupés (en gris) :
et vous voulez trouver tous les rectangles de dimensions données , disons 3x5. Vous pouvez le faire très efficacement en deux passes linéaire O(n) temps algorithme (n étant le nombre de sièges) :
1) dans un premier passage , allez par colonnes, de bas en haut, et pour chaque siège, indiquez le nombre de sièges consécutifs disponibles jusqu'à celui-ci :
répéter, jusqu'à :
2) en un second passage , passez par lignes, et recherchez au moins 5 nombres consécutifs supérieurs ou égaux à 3 :
donc, finalement, vous obtenez :
ce qui donne la solution :ces séquences de nombres (zones vertes) sont les bords supérieurs des 2 rectangles possibles 3x5 de sièges libres.
L'algorithme pourrait être facilement amélioré, par ex. obtenir tous les rectangles avec une aire maximale. Ou, il pourrait être utilisé pour trouver toutes les régions continues (pas seulement en forme de rectangle) de N sièges - juste, lors de la deuxième passe, recherchez une séquence continue de nombres qui résume au moins N.
