Nehmen Sie ein boolesches Array an, wie:

1111
1111
1110
1111
1001

Nun müssen Sie den Weg finden, die kleinsten Rechtecke einer Größe anzuordnen, um diese Form zu erreichen. So würden Sie zum Beispiel Folgendes finden:

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

Wobei + eine Ecke eines Rechtecks ​​und |, - Ränder eines Rechtecks ​​sind.

Was ich darüber nachgedacht habe, ist, mit dem größtmöglichen Rechteck zu beginnen und zu prüfen, ob es eine Stelle im Array gibt, an der es platziert werden kann, wo jedes vom Rechteck abgedeckte Array-Element wahr ist. Wenn ein solcher Ort existiert, wird das Rechteck zu einer Liste hinzugefügt. Danach prüfen wir im linken Bereich des Arrays, ob es einen anderen Punkt gibt, in den das Rechteck eingefügt werden soll, verringern die Größe des Rechtecks ​​und wiederholen den Vorgang mit dem verbleibenden Bereich, bis die Größe 0 ist.

Dies sollte zu guten Ergebnissen führen, da wir immer mit großen Rechtecken beginnen, von denen wir natürlich weniger verwenden können, was wiederum bedeutet, dass wir kleine Mengen von Rechtecken verwenden.

Dies ist jedoch nur ein Konzept, über das ich nachgedacht und das ich noch nicht in die Praxis umgesetzt habe. Es scheint ziemlich ineffizient zu sein, also habe ich mich gefragt, ob es bekannte schnelle Algorithmen gibt, um dies zu erreichen?