Algorithm (DP)

1. We can construct a unweighted directed graph $G=(V,E)$ among all taps. For any two vertices $v_{i}$ and $v_{j}$, there is an edge if $$i<j\text{ and }[i-\text{range}[i],i+\text{range}[i]]\cap[j-\text{range}[j],j+\text{range}[j]]\neq\emptyset.$$
2. Then the problem is transformed to finding the minimum distance from $v_{0}$ to $v_{n},$ which is a classical dynamic programming problem with objective $$f(v)=\begin{cases} \min_{u\in\text{neighbor}(v)}\{f(u)+1\} & \text{if }\text{neighbor}(v)\neq\emptyset\\\\ \infty & \text{else} \end{cases}$$

Algorithm (Greedy)

1. We remove nested intervals and only retain the outer most ones. Then we sort the remaining ones by end points in increasing order.
2. Then we greedily maximize the cover using a linear scan.
3. The correctness of this algorithm can be proved using an exchange argument.

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F>
recursive(F)->recursive<F>;
auto const rec = [](auto f) { return recursive{std::move(f)}; };

template <class F, class... Gs>
auto compose(F&& f, Gs&&... gs) {
  return [f, gs...](auto&&... args) {
    return f(gs(std::forward<decltype(args)>(args)...)...);
  };
}

class Solution {
 public:
  int minTaps(int n, vector<int>& ranges) {
    const struct {
      mutable optional<int> f[10005];
    } memo;

    const auto G = [&](vector<vector<int>> self = {}) {
      self.resize(n + 1, vector<int>{});
      for (int i = 0; i < size(ranges); ++i) {
        const auto [ll, rr] = pair(std::max(0, i - ranges[i]), std::min(n, i + ranges[i]));
        for (int v = ll; v < rr; ++v) {
          self[rr].emplace_back(v);
        }
      }
      return self;
    }();

    auto f = rec([&, memo = std::ref(memo.f)](auto&& f, int i) {
      if (memo[i])
        return memo[i].value();
      else
        return *(memo[i] = [&] {
          if (i == 0)
            return 0;
          else 
            return [&](int acc = INT_MAX / 2) {
              for (const auto v : G[i])
                acc = std::min(acc, f(v) + 1);
              return acc;
            }();
        }());
    });

    const auto solution = [&] {
      const auto fn = f(n);
      return fn == INT_MAX / 2 ? -1 : fn;
    }();

    return solution;
  }
};

namespace greedy {
class Solution {
 public:
  int minTaps(int n, vector<int>& ranges) {
    auto comp = [&](auto& a, auto& b) {
      if (a[1] == b[1])
        return a[0] < b[0];
      else
        return a[1] > b[1];
    };

    auto make_sorted = [&](const vector<int>& x) {
      auto self = vector<vector<int>>{};
      for (int i = 0; i < size(x); ++i)
        self.emplace_back(vector<int>{std::max(i - x[i], 0), std::min(n, i + x[i])});
      return std::sort(begin(self), end(self), comp), self;
    };

    auto id = [](const auto& x) { return x; };

    auto make_trimmed = [&](const vector<vector<int>>& x) {
      auto acc = vector<vector<int>>{};

      struct state_t {
        int start;
        int end;
      };

      for (auto [i, state] = tuple(0, state_t{0, 0}); i < size(x); ++i) {
        const auto [cur_start, cur_end] = tuple(x[i][0], x[i][1]);
        if (i == 0) {
          acc.emplace_back(x[i]);
          state = {cur_start, cur_end};
        }
        else if (state.start <= cur_start and cur_end <= state.end)
          state = id(state);
        else {
          acc.emplace_back(x[i]);
          state = {cur_start, cur_end};
        }
      }
      return std::sort(begin(acc), end(acc), std::not_fn(comp)), acc;
    };

    auto intersect = [&](int l1, int r1, int l2, int r2) {
      return l1 <= l2 and l2 <= r1 and r1 <= r2;
    };

    const auto solution = [&] {
      struct state_t {
        int ll;
        int rr;
        bool new_interval;
      };

      const auto data = compose(make_trimmed, make_sorted)(ranges);

      const auto [L, R, C] = [&](int lacc = INT_MAX, int racc = INT_MIN, int count = 0) {
        for (auto [i, state] = tuple(0, state_t{0, -1, -1}); i < size(data) and count != -1; ++i) {
          const auto [cur_ll, cur_rr]       = pair(data[i][0], data[i][1]);
          const auto [ll, rr, new_interval] = state;
          if (i == 0) {
            count++;
            state = {cur_ll, cur_rr, true};
          }
          else if (intersect(ll, rr, cur_ll, cur_rr) and new_interval) {
            count++;
            racc  = std::max(racc, cur_rr);
            state = {ll, rr, false};
          }
          else if (intersect(ll, rr, cur_ll, cur_rr) and not new_interval) {
            racc  = std::max(racc, cur_rr);
            state = {ll, rr, false};
          }
          else if (intersect(lacc, racc, cur_ll, cur_rr)) {
            if (i + 1 < size(data) and intersect(lacc, racc, data[i + 1][0], data[i + 1][1]))
              state = {ll, rr, false};
            else {
              count++;
              racc  = std::max(racc, cur_rr);
              state = {cur_ll, cur_rr, true};
            }
          }
          else
            count = -1;
        }
        return tuple(lacc, racc, count);
      }();

      if (C == -1)
        return -1;
      else
        return (L == 0 and R == n) ? C : -1;
    }();

    return solution;
  }
};
}  // namespace greedy