Este problema é muito melhor resolvido fora do mysql, em outra linguagem. Em outras palavras, você tem uma matriz de assentos, alguns dos quais estão ocupados (cinza):
e você deseja encontrar todos os retângulos de determinadas dimensões , digamos 3x5. Você pode fazer isso de forma muito eficiente por duas passagens linear
O(n)
hora algoritmo (n sendo o número de assentos):1) em uma primeira passagem , passe por colunas, de baixo para cima, e para cada assento, indique o número de assentos consecutivos disponíveis até este:
repetir até:
2) em uma segunda passagem , vá por linhas e procure pelo menos 5 números consecutivos maiores ou iguais a 3:
então, finalmente, você obtém:
que dá a solução:essas sequências numéricas (áreas verdes) são as bordas superiores dos 2 possíveis retângulos 3x5 de assentos livres.
O algoritmo pode ser facilmente melhorado para, e. obter todos os retângulos com área máxima. Ou, poderia ser usado para encontrar quaisquer regiões contínuas (não apenas em forma de retângulo) de N assentos - apenas, durante a segunda passagem, procure uma sequência contínua de números que soma pelo menos N.