leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1326.cpp (608B)

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