I came up with a general O(n^2) algorithm that yields 30 rectangles, which is one off from the optimal answer according to you. Actually, it's only O(n^2) because I'm exhaustively searching an array instead of indexing by xy coordinates in nested hashes, which would yield O(n).

Basically, it just fills the spaces with rectangles, expanding horizontally. Then I look for "stacks" of vertical adjacent rectangles and combine them.

(EDIT: Goes to show that you can get pretty good though non-optimal results by taking the low hanging fruit and optimizing a bit.)