FastPrep
Problem · Array

Minimum Sprinklers to Cover an Interval

Learn this problem
● HardQuince logoQuinceNEW GRADOA

Problem statement

An interval from 0 through n must be completely covered by sprinklers.

There are n + 1 sprinklers. Sprinkler i is located at position i. When activated, it covers the continuous interval from i - ranges[i] through i + ranges[i], clipped to the target interval [0, n].

Return the minimum number of sprinklers that must be activated to cover every point in [0, n]. Return -1 if complete coverage is impossible.

Function

minSprinklers(n: int, ranges: int[]) → int

Examples

Example 1

n = 5ranges = [3,4,1,1,0,0]return = 1

Activating the sprinkler at position 1 covers the entire target interval [0, 5], so one sprinkler is sufficient and optimal.

Example 2

n = 3ranges = [0,0,0,0]return = -1

Every sprinkler covers only its own position, leaving gaps between positions. The full interval cannot be covered.

Example 3

n = 7ranges = [1,2,1,0,2,1,0,1]return = 3

Sprinklers at positions 1, 4, and 7 cover [0, 3], [2, 6], and [6, 7]. Together they cover the target interval, and no pair can reach from 0 through 7.

Constraints

  • 1 <= n <= 10000
  • ranges.length = n + 1
  • 0 <= ranges[i] <= n

More Quince problems

drafts saved locally
public int minSprinklers(int n, int[] ranges) {
  // write your code here
}
n5
ranges[3,4,1,1,0,0]
expected1
checking account