All problems

Minimum Number of Taps to Open to Water a Garden

Hard · intervals

A flower bed lies along a straight line, from position 0 to position n. There is a tap at every whole position 0, 1, 2, ..., n, so there are n + 1 taps. When the tap at position i is opened, it waters every point from i - ranges[i] to i + ranges[i]. A tap with range 0 waters only its own spot. A tap may water beyond the ends of the bed, and that is fine.

Open as few taps as possible so that every point of the bed, from 0 to n, is watered. Two taps whose watered stretches meet at a single point leave no dry gap there.

Return the smallest number of taps to open, or -1 if no choice of taps waters the whole bed.

Examples

Example 1

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

Output: 1

The tap at position 1 waters from -3 to 5, which already covers the whole bed.

Example 2

Input: n = 3, ranges = [0, 0, 0, 0]

Output: -1

Every tap waters only its own spot, so the stretches between them stay dry.

Example 3

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

Output: 3

Open the taps at positions 1 (waters -1 to 3), 4 (2 to 6) and 7 (6 to 8). No pair of taps reaches both ends.

Constraints