CODEWITHSUNDEEP
algorithm
Bruce
Bruce

Reputation: 21

How to compute the minimum number of rectangles required to cover occupied cells in a grid?

Given an R×C grid, out of which certain cells are occupied, what is the minimum number of rectangles needed to cover the occupied cells?

Example:

x - - - -
- - x - -
- x - x x
x - x - -

Here x and - mark occupied and unoccupied cells, respectively.

The minimum number of rectangles necessary in this case is 3. (Cover column 1, column 2, and row 3.)

Can anyone point me to the right direction? This seems easy enough, but I’m not able to arrive at a robust solution!

Upvotes: 2

Views: 993

Answers (1)

Evgeny Shavlyugin
Evgeny Shavlyugin

Reputation: 421

Consider a bipartite graph consisting of two sets of vertices, with the vertices in the first set corresponding to the rows, and the vertices from the second set corresponding to the columns of the grid. A vertex i from the first set is connected to a vertex j from the second set iff a[i][j] == 'x'.

Then the problem is reduced to finding a minimum vertex cover of this graph, i.e., the smallest set of vertices such that each edge of the graph has at least one of its endpoints present in this set. As the graph is bipartite, a minimum vertex cover can be computed in polynomial time; see this post.

Upvotes: 2

Related Questions