Minimum Number of Taps to Open to Water a Garden LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minTaps(int n, vector<int> &ranges) {
4
    vector<pair<int, int>> v;
5
    for (int i = 0; i < ranges.size(); i++) {
6
      // making ranges
7
      v.push_back({i - ranges[i], i + ranges[i]});
8
    }
9
    // sorting the intervals
10
    sort(v.begin(), v.end());
11

12
    // to keep track from where we need to cover
13
    int uncovered = 0;
14
    int idx = 0;
15
    // number of ranges used
16
    int cnt = 0;
17

18
    // to check if its possible
19
    bool ok = true;
20

21
    // as long as we have not covered the garden
22
    while (uncovered < n) {
23
      // we will try to cover the uncovered such that new uncovered is maximum
24
      // possible
25
      int new_uncovered = uncovered;
26
      while (idx < n + 1 && v[idx].first <= uncovered) {
27
        new_uncovered = max(new_uncovered, v[idx].second);
28
        idx++;
29
      }
30
      // we have used one range
31
      cnt++;
32

33
      // it means we were not able to cover with ranges so not possible
34
      if (new_uncovered == uncovered) {
35
        ok = false;
36
        break;
37
      }
38
      // updating uncovered for next iteration
39
      uncovered = new_uncovered;
40
    }
41
    if (ok) return cnt;
42
    return -1;
43
  }
44
};