Ten problem jest znacznie lepiej rozwiązywany poza mysql, w innym języku. Innymi słowy, masz matrycę miejsc, z których część jest zajęta (szare):
i chcesz znaleźć wszystkie prostokąty o podanych wymiarach , powiedzmy 3x5. Możesz to zrobić bardzo wydajnie za pomocą dwuprzebiegowego liniowego O(n) czas algorytm (n to liczba miejsc):
1) w pierwszym przejściu , przejdź kolumnami od dołu do góry i dla każdego miejsca podaj liczbę kolejnych dostępnych miejsc aż do tego jednego:
powtarzaj, aż:
2) w drugim przejściu , przejdź przez wiersze i poszukaj co najmniej 5 kolejnych liczb większych lub równych 3:
więc w końcu otrzymujesz:
co daje rozwiązanie:te sekwencje liczb (zielone obszary) to górne krawędzie 2 możliwych prostokątów 3x5 wolnych miejsc.
Algorytm można by łatwo rozbudować m.in. zdobądź wszystkie prostokąty o maksymalnej powierzchni. Lub może być użyty do znalezienia dowolnych ciągłych regionów (nie tylko w kształcie prostokąta) N miejsc - po prostu podczas drugiego przejścia poszukaj ciągłego ciągu liczb, który sumuje się do co najmniej N.
