leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1326.cpp (608B)

      1 class Solution {
      2   public:
      3     int minTaps(int n, const vector<int> &ranges) {
      4         vector<int> reach(n + 1);
      5         for (int i = 0; i < ranges.size(); i++) {
      6             int start = max(i - ranges[i], 0);
      7             int end = min(n, i + ranges[i]);
      8             reach[start] = max(reach[start], end);
      9         }
     10 
     11         int res = 0, crnt = 0, next = 0;
     12         for (int i = 0; i <= n; i++) {
     13             if (i > next) return -1;
     14             if (i > crnt) {
     15                 res++;
     16                 crnt = next;
     17             }
     18             next = max(next, reach[i]);
     19         }
     20 
     21         return res;
     22     }
     23 };