Minimum Sprinklers to Cover Garden | Dataford Interview Questions

Minimum number of sprinklers to cover the full range (LC 1326 Minimum Number of Taps to Open to Water a Garden)

Asked in the OA stage.

Implement min_sprinklers(n, ranges), where n is the endpoint of a one-dimensional garden interval [0, n], and ranges[i] is the coverage radius of the sprinkler at position i. Return the minimum number of sprinklers needed to cover the full interval, or -1 if coverage is impossible.

Input: integer n and an integer array ranges of length n + 1.

Output: an integer minimum count.

Examples:

n = 5, ranges = [3,4,1,1,0,0] returns 1.
n = 3, ranges = [0,0,0,0] returns -1.

Constraints: 1 <= n <= 1000; len(ranges) = n + 1; 0 <= ranges[i] <= n.

Constraints

1 <= n <= 1000
len(ranges) == n + 1
0 <= ranges[i] <= n
Return -1 when complete coverage is impossible

Function Signature

def min_sprinklers(n, ranges):

Your question is Minimum Sprinklers to Cover Garden. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem