There is a one-dimensional garden of length n - 1
meters. Every 1
meter there is a sprinkler,
and each sprinkler has a different covering range. The sprinklers are labelled 0 ~ n - 1
,
indicating that the sprinklers are 0 ~ n - 1
meters away from the start of the fountain.
The i
th sprinkler covers r[i]
meters of land, meaning that everywhere from
i - r[i]
meters to i + r[i]
meters (inclusive) will be covered by the sprinkler.
This is a companion discussion topic for the original entry at https://algo.monster/problems/twitter_oa_activate_fountain/