# Minimum Number of Rectangles Needed to Cover a set of square in an $\text{N} \times \text{N}$ grid

There is an $\text{N} \times \text{N}$ grid of squares. Some arbitrary subset of those squares must be covered by some number of rectangles (a given square must be covered entirely by one rectangle, rectangles can only cover these ares, not anything else). How can I find the set of rectangles that covers all of a given set of squares with the smallest possible number of rectangles?

What is the maximum number of rectangles needed to fill in any subset of an $\text{N} \times \text{N}$ square?

This is the Rectilinear Picture Compression problem that is known to be NP-hard (see textbook Computer and Intractability, a guide to the theory of NP-completeness by Garey and Johnson, p. 232, SR25). So noone will give you polynomial time solution if $\mathrm{P} \ne \mathrm{NP}$. You can apply methods for solving NP-hard problems, e. g., brunch and bounds.
EDIT: The note above was about cover-version of problem. For partition-version there are polynomial time algorithms. You can start from Efficient Algorithms for Geometric Graph Search Problems by Hiroshi Imai and Takao Asano, subsection 7.1. As far as I see for your case it provides $O(N^{5/2})$-time algorithm for a single connected region of squares and therefore $O(N^{7/2})$-time in total.
It seems that painting grid like chess board gives maximum number $\left\lceil\frac{N^2}2\right\rceil$ of rectangles needed, however I can't give rigorous proof now.