1326. Minimum Number of Taps to Open to Water a Garden

题目信息

题号:

1326

难度:

Hard

主题:

区间覆盖、贪心、动态规划

原题:

LeetCode 1326

重点:

第 i 个水龙头覆盖 [i-ranges[i], i+ranges[i]] 与花园的交集;用最少区间完整覆盖 [0,n]

题目重述

花园位于数轴区间 [0,n]。位置 i 有一个水龙头,打开后可浇灌从 i-ranges[i] 到 i+ranges[i] 的范围,超出花园部分忽略。

请选择最少数量的水龙头,使整个闭区间 [0,n] 都被覆盖。若无法完整覆盖,返回 -1。

1 <= n <= 10^4,ranges.length == n + 1,0 <= ranges[i] <= 100。

自建示例

两个重叠区间可以覆盖整座花园:

输入:n = 5, ranges = [1,2,1,0,2,1]
输出:2
解释:位置 1 覆盖 [0,3],位置 4 覆盖 [2,5],二者并集覆盖整个花园。

覆盖在中途断开时无解:

输入:n = 5, ranges = [3,0,0,0,0,0]
输出:-1
解释:唯一有效水龙头只覆盖 [0,3],区间 (3,5] 无法浇灌。