Open the Minimum Number of Sprinklers to Cover a Garden

Problem Statement

You are tasked with watering a garden represented as a line segment from 0 to L. You are given n sprinklers. Each sprinkler i is located at position p[i] and has a range r[i], meaning it covers the interval [p[i] - r[i], p[i] + r[i]].

Your goal is to select the minimum number of sprinklers needed such that the entire interval [0, L] is covered. If it is impossible to cover the garden, return -1.

Function Signature

def min_sprinklers(L, p, r) -> int:

Examples

Example 1:

• L = 10, p = [1, 3, 5, 8], r = [2, 2, 2, 2]
• Intervals: [-1, 3], [1, 5], [3, 7], [6, 10]
• Output: 3 (e.g., using intervals [-1, 3], [3, 7], [6, 10] covers [0, 10])

Example 2:

• L = 5, p = [1, 2], r = [0.5, 0.5]
• Output: -1 (Gaps exist in the coverage).

Constraints

• 0 <= L <= 10^6
• 1 <= n <= 10^5
• -10^6 <= p[i] <= 10^6
• 0 <= r[i] <= 10^6

Edge Cases

• The garden is already covered with one sprinkler.
• No combination of sprinklers can bridge the gap between 0 and L.
• Sprinklers may have negative coverage ranges (outside the [0, L] bounds).