When I solved this problem first I wrote a brute-force for small cases to check for a "pattern". If you see the "pattern" then you can come up with a greedy solution. Maybe it will be good idea to train your brute-force skills, nonetheless, here is my brute-force for checking the pattern

http://pastebin.com/qMZ4w0fp