Comment by 256

This is indeed an interesting problem. If you just want to minimize the number of rectangles there is a neat solution on stackoverflow [1] that uses minimum vertex cover (equivalently, bipartite maximum matching).

[1] https://stackoverflow.com/a/6634668