Supongamos una matriz booleana como:

1111
1111
1110
1111
1001

Ahora necesitas encontrar la forma de organizar los rectángulos mínimos de cualquier tamaño para lograr esta forma. Entonces, por ejemplo, encontrarías esto:

+-++
| |+
| |
+-++
+  +

Donde + es una esquina de un rectángulo y |, - bordes de un rectángulo.

Lo que pensé en hacer es comenzar con el rectángulo más grande posible, verificando si hay algún lugar en la matriz donde se pueda colocar, donde todo elemento de la matriz cubierto por el rectángulo sea verdadero. Si tal lugar existe, el rectángulo se agregaría a una lista. Luego verificamos en el espacio izquierdo de la matriz si hay otro lugar para colocar el rectángulo, luego disminuimos el tamaño del rectángulo y repetimos el proceso con el espacio restante hasta que el tamaño sea 0.

Esto debería dar buenos resultados ya que siempre comenzamos con rectángulos grandes, que podemos, por supuesto, usar menos, lo que a su vez significa que estamos usando pequeñas cantidades de rectángulos.

Sin embargo, este es solo un concepto que he pensado y que aún no he puesto en práctica. Parece bastante ineficiente, así que me preguntaba si habría algoritmos rápidos conocidos para lograrlo.