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.

Expected approach

• Convert to interval covering: each sprinkler i → [max(0, i−p[i]), min(n, i+p[i])]. Precompute maxReach[l] = furthest right end among intervals starting at or before l. Greedy jump-game sweep: from current covered end end, extend to the best reach among intervals starting <= end+ (contiguous coverage), count++; stuck (no progress) → -1. O(n) after O(n) preprocessing. Identical skeleton to Jump Game II / Video Stitching / Minimum Taps — naming the reduction is the point; watch closed-vs-continuous coverage semantics (points vs unit segments).