Tento problém se mnohem lépe řeší mimo mysql, v jiném jazyce. Jinými slovy, máte matici sedadel, z nichž některá jsou obsazená (šedá):
a chcete najít všechny obdélníky daných rozměrů řekněme 3x5. Můžete to udělat velmi efektivně dvouprůchodovým lineárním O(n)
časa algoritmus (n je počet míst):
1) v prvním průchodu , přejděte po sloupcích zdola nahoru a pro každé sedadlo označte počet po sobě jdoucích sedadel, která jsou k dispozici až do tohoto:
opakujte, dokud:
2) ve druhém průchodu , přejděte po řádcích a hledejte alespoň 5 po sobě jdoucích čísel větších nebo rovných 3:
takže konečně dostanete:
což dává řešení:tyto číselné řady (zelené oblasti) jsou horními okraji 2 možných obdélníků 3x5 volných míst.
Algoritmus lze snadno rozšířit např. získat všechny obdélníky s maximální plochou. Nebo by se dal použít k nalezení jakýchkoliv souvislých oblastí (nejen ve tvaru obdélníku) N sedadel – stačí během druhého průchodu vyhledat souvislou posloupnost čísel, která dává součtu alespoň N.