3 ms·

I feel stupid now.

• darylteo 13y ago
  Don't be. These kinds of problems are algorithmic problems and have very little bearing on your capabilities as a developer from an engineering perspective. 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.
  • rav 13y ago
    > 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 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.