Questo problema è risolto molto meglio al di fuori di MySQL, in un'altra lingua. In altre parole, hai una matrice di posti, alcuni dei quali sono occupati (quelli grigi):
e vuoi trovare tutti i rettangoli di determinate dimensioni , diciamo 3x5. Puoi farlo in modo molto efficiente con due passaggi linear O(n) tempo algoritmo (n è il numero di posti):
1) in un primo passaggio , vai per colonne, dal basso verso l'alto, e per ogni posto, indica il numero di posti consecutivi disponibili fino a questo:
ripetere, fino a:
2) in un secondo passaggio , vai per righe e cerca almeno 5 numeri consecutivi maggiori o uguali a 3:
quindi, finalmente, ottieni:
che fornisce la soluzione:queste sequenze numeriche (aree verdi) sono i bordi superiori dei 2 possibili rettangoli 3x5 di posti liberi.
L'algoritmo potrebbe essere facilmente migliorato ad es. ottieni tutti i rettangoli con area massima. Oppure, potrebbe essere utilizzato per trovare qualsiasi regione continua (non solo a forma di rettangolo) di N sedi - solo, durante il secondo passaggio, cercare una sequenza continua di numeri che riassuma almeno N.
