Minimum Sprinklers to Water a Garden

Problem A linear garden [0, n] has a sprinkler at each point i with power p[i], watering [i − p[i], i + p[i]]. Activate the minimum number of sprinklers to water the whole garden, or return -1.

Input / Output

• Input: int n (garden length), int array p (n+1 sprinklers). Output: min sprinklers or -1.

Constraints

• n up to 10^5; O(n) after the interval conversion expected.

Example

• n = 5, p = [1,2,1,1,2,1]: sprinkler 1 covers [-1,3]→[0,3], sprinkler 4 covers [2,6]→[2,5] → 2 sprinklers.