(Offtopic rant) Guess, I'm not really suited for programming. When I read I remembered I've heard about an algorithm for such tasks, Googled the details up to freshen my memory, and things instantly became boring. :(
Sadly, JavaScript.
#SadlyJavascript
If you can integrate haste or fay and let people play in Haskell that would be indeed be epic, and I would definitely use it (as haskell is my learning project at the moment)
I don't know Haskell, but I would have considered learning it if it was offered. ;)
There are at least three of them already - UHC's JS backend, Haste and Fay.
Could be fun.
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.)
For me, its like saying someone who is poor at physics makes a poor accountant.
While a fun exercise, I feel that it doesn't actually test for actual programming ability as it actually requires the programmer to be familiar with this particular subset of algorithms first (something that isn't entirely fundamental imho). I do not believe many jobs require the skillset that this problem tests for.
For example, I had very little idea how to approach this problem in an optimal way. But once I read the comment above I figured out a pretty brute force method. You can get 34 by just joining contiguous segments in each column with segments in their neighbouring columns if they have the same row and height. With some trimming I managed to get 30... not really sure if 29 is actually possible actually, I can't find where I can cut down on 1 more.
Edit: found it. Very tricky edge case with my algorithm. Happy with 30.
I don't think you are required to know this particular subset of algorithms first -- I certainly did not, and it took me about half an hour of searching around the net until I found the right terms to use.
Perhaps max cardinality bipartite matching is something I know from my first year at CS, but I didn't know its application to this problem before I had read through several different answers on StackExchange.
The general version of this problem can be termed "the minimum dissection of a rectilinear region" and can be solved optimally using a sweep-line and computing the maximal independent set in a bipartite graph as described in section 7.1 of [1].
Now if you'll excuse me, I'm gonna have some fun implementing this result in JavaScript.
[1] Hiroshi Imai, Takao Asano: Efficient algorithms for geometric graph search problems (1986) https://dl.acm.org/citation.cfm?id=14098 http://epubs.siam.org/doi/pdf/10.1137/0215033