Optimal Sprinkler Coverage (Hard) — Practice with Code Visualizer

You are managing an irrigation system for a linear garden bed that extends along a straight path from position 0 to position n (representing n units of length). Along this garden bed, there are n + 1 sprinkler heads installed at consecutive integer positions [0, 1, 2, ..., n].

Each sprinkler head has a specific coverage radius. The sprinkler at position i has a coverage radius of ranges[i], meaning when activated, it can water the continuous segment from position max(0, i - ranges[i]) to position min(n, i + ranges[i]).

Your objective is to determine the minimum number of sprinkler heads that need to be activated to ensure the entire garden bed from position 0 to position n receives water coverage. Every point along the garden must be covered by at least one active sprinkler.

If it is impossible to achieve complete coverage of the garden using the available sprinklers (regardless of which ones are activated), return -1.

Key Observations:

A sprinkler with ranges[i] = 0 can only cover its own position i and nothing else.
Sprinklers near the beginning might extend to negative positions (before position 0), but only the portion from 0 onward matters.
Similarly, sprinklers near the end might extend beyond position n, but only coverage up to position n is relevant.
The goal is to minimize the count of active sprinklers, not to minimize total water usage or overlap.

Each sprinkler's coverage range is as follows: • Sprinkler at position 0: covers [-3, 3], effectively [0, 3] • Sprinkler at position 1: covers [-3, 5], effectively [0, 5] • Sprinkler at position 2: covers [1, 3] • Sprinkler at position 3: covers [2, 4] • Sprinkler at position 4: covers [4, 4] • Sprinkler at position 5: covers [5, 5]

Activating only the sprinkler at position 1 provides complete coverage from position 0 to position 5, making the minimum number of sprinklers needed equal to 1.

Each sprinkler has a range of 0, meaning: • Sprinkler at position 0: covers only [0, 0] • Sprinkler at position 1: covers only [1, 1] • Sprinkler at position 2: covers only [2, 2] • Sprinkler at position 3: covers only [3, 3]

While each individual position is covered by its corresponding sprinkler, the gaps between positions (e.g., from 0.5, 1.5, 2.5) are not covered. Since sprinklers only cover their exact positions with no overlap, complete continuous coverage from 0 to 3 is impossible. Therefore, return -1.

Analyzing the sprinkler coverage: • Sprinkler at position 0: covers [-2, 2], effectively [0, 2] • Sprinkler at position 1: covers only [1, 1] • Sprinkler at position 2: covers only [2, 2] • Sprinkler at position 3: covers only [3, 3] • Sprinkler at position 4: covers [2, 6], effectively [2, 5] • Sprinkler at position 5: covers only [5, 5]

By activating sprinklers at positions 0 and 4, we achieve coverage: [0, 2] ∪ [2, 5] = [0, 5]. The minimum number of sprinklers needed is 2.