Este problema se resuelve mucho mejor fuera de mysql, en otro idioma. En otras palabras, tienes una matriz de asientos, algunos de los cuales están ocupados (grises):
y desea encontrar todos los rectángulos de dimensiones dadas , digamos 3x5. Puede hacer esto de manera muy eficiente mediante dos pasos lineal O(n) tiempo algoritmo (siendo n el número de asientos):
1) en una primera pasada , vaya por columnas, de abajo hacia arriba, y para cada asiento, indique el número de asientos consecutivos disponibles hasta este:
repetir, hasta que:
2) en una segunda pasada , ve por filas y busca al menos 5 números consecutivos mayores o iguales a 3:
entonces, finalmente, obtienes:
lo que da la solución:estas secuencias de números (áreas verdes) son los bordes superiores de los 2 posibles rectángulos de 3x5 de asientos libres.
El algoritmo podría mejorarse fácilmente para, p. obtener todos los rectángulos con área máxima. O bien, podría usarse para encontrar cualquier región continua (no solo en forma de rectángulo) de N asientos; solo, durante el segundo pase, busque una secuencia continua de números que sume al menos N.
