# How to efficiently divide a grid with some predefined sub-rectangles?

Given an $M$x$N$ grid with some predefined sub-rectangles. How to divide the grid into a set of sub-rectangles, which contains the predefined sub-rectangles, so that its the number of elements is minimum and no sub-rectangle is overlapped ?

Is there any reference to the problem and it's solutions ? Is the problem NP-Hard ?

For example: A grid contains 2 predefined (black) sub-rectangles might be divided as follow:

• Had I had time, I would have written an algorithm of linear-log time-complexity. – John L. Sep 9 '18 at 6:20