Masalah ini jauh lebih baik diselesaikan di luar mysql, dalam bahasa lain. Dengan kata lain, Anda memiliki matriks kursi, beberapa di antaranya terisi (abu-abu):
dan Anda ingin menemukan semua persegi panjang dengan dimensi tertentu , katakanlah 3x5. Anda dapat melakukannya dengan sangat efisien dengan dua pass linear O(n) waktu algoritma (n adalah jumlah kursi):
1) dalam umpan pertama , menurut kolom, dari bawah ke atas, dan untuk setiap kursi, menunjukkan jumlah kursi berurutan yang tersedia hingga yang ini:
ulangi, sampai:
2) dalam umpan kedua , per baris, dan cari setidaknya 5 angka berurutan lebih besar atau sama dengan 3:
jadi, akhirnya, Anda mendapatkan:
yang menghasilkan solusi:barisan angka ini (area hijau) adalah tepi atas dari 2 kemungkinan persegi panjang 3x5 tempat duduk kosong.
Algoritme dapat dengan mudah ditingkatkan ke mis. dapatkan semua persegi panjang dengan luas maksimum. Atau, ini dapat digunakan untuk menemukan daerah bersambungan (tidak hanya berbentuk persegi panjang) dari N kursi - cukup, selama lintasan kedua, cari urutan bilangan kontinu yang berjumlah setidaknya N.
