Minimum Number of Taps to Open to Water a Garden

Hard

A garden is a one-dimensional interval [0, k]. There are nums.length == k + 1 taps, one at each integer point i. Tap i waters the area [i - nums[i], i + nums[i]]. Return the minimum number of taps to open so the whole garden is watered, or -1 if it is impossible.

Example 1

Input:  ranges = [3,4,1,1,0,0], n = 5
Output: 1

Example 2

Input:  ranges = [0,0,0,0], n = 3
Output: -1

Example 3

Input:  ranges = [1,2,1,0,2,1,0,1], n = 7
Output: 3

Constraints

• 1 <= k <= 10^4
• nums.length == k + 1
• 0 <= nums[i] <= 100