ก๊อกน้ำขั้นต่ำเพื่อรดน้ำสวนใน C++

คำอธิบายโจทย์

สวน 1 มิติ ตำแหน่ง 0 ถึง n มีก๊อก n+1 ตัวที่ตำแหน่ง 0..n ก๊อก i รดน้ำได้ [i-ranges[i], i+ranges[i]] หาจำนวนก๊อกน้อยที่สุดที่เปิดเพื่อครอบคลุมทั้งสวน ไม่ได้คืน -1

ตัวอย่าง

n=5, ranges=[3,4,1,1,1,0] → Output: 1

ก๊อก index 1 ครอบคลุม [-3,5] ครอบคลุมทั้งสวน

วิธีแก้ปัญหา (Greedy + Interval Coverage)

1. สร้างอาร์เรย์ v: v[left] = right สูงสุดที่เริ่มจาก left
2. เริ่มจาก v[0] ถ้า -1 → -1
3. ใช้ greedy: ขยาย curr ไป next สูงสุดในช่วง [i..curr] นับจำนวนก๊อก

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        int ret = 1;
        vector<int> v(n+1, -1);
        
        for(int i=0; i<=n; i++) {
            int u = max(i - ranges[i], 0);
            int e = min(n, i + ranges[i]);
            v[u] = max(v[u], e);
        }
        if(v[0] == -1) return -1;
        
        int curr = v[0], i = 0, next = 0;
        while(curr < n) {
            while(i <= curr) {
                next = max(next, v[i]);
                i++;
            }
            if(next == curr) return -1;
            curr = next;
            ret++;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,4,1,1,1,0};
    cout << ob.minTaps(5, v);
    return 0;
}

อินพุต

5, {3,4,1,1,1,0}

เอาต์พุต

1