I got this problem as part of a technical assessment for a job. I implemented the greedy algorithm instead of the optimal dynamic programming solution.
I have seen this problem before but never bothered solving it. I am just wondering whether it was reasonable to assume that this problem can be solved in 30 minutes by someone who has never solved it using the optimal dynamic programming solution before.