Mysql
 sql >> Base de Dados >  >> RDS >> Mysql

Matriz de pesquisa para todos os retângulos de determinadas dimensões (selecione blocos de assentos)


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.