Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
What if we sort the intervals? Considering the sorted intervals, how can we solve the problem with dynamic programming?
Let's consider a DP(pos, limit) where pos represents the position of the current interval we are gonna take the decision and limit is the current covered area from [0 - limit]. This DP returns the minimum number of taken intervals or infinite if it's not possible to cover the [0 - T] section.