Solution by Inelus Gabriel Robert
There are solutions of varied complexities. An O(N2) algorithm will build a graph and do a Breadth-First Search.
The O(N) solution uses a dynamic programming approach. Let dp[i] = the least number of sick leaves needed for days i, i+1, …, D, D+1.
Initialisation
- dp[i] = infinity, ∀ i ∈ [1, D]
- dp[D+1] = 0
Recurrence relation
- dp[i] = min(dp[i], dp[i+1]), provided that Lumber Jack did not skip the ith day.
- dp[i] = min(dp[i], dp[next] + 1), provided that we have a sick leave on interval [i, next).
The dp[] table can be computed from high indices to low.
Hence, we can build a graph with an edge (i) → (next+1) in linear time using linked lists (or STL vectors) and then apply the above recurrence relation.
The final complexity is O(N) both time and space.
Note that given the low score of the problem, we accept slightly worse complexity solutions, however exponential complexities are not acceptable.
