[LeetCode] 1326. Minimum Number of Taps to Open to Water a Garden

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/

Minimum Number of Taps to Open to Water a Garden - LeetCode

문제 유형 : 그리디

문제 난이도 : Hard

 

문제

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

 

1차원적인 정원이 있다. 0부터 n까지의 자리가 있고. 수도꼭지를 개방할 수 있는 범위 ranges가 주어진다. 전체 정원을 덮는 최소 수도꼭지를 여는 횟수를 반환하라. 못 연다면 -1을 반환하라.

 

풀이

실제 물을 뿌리는 범위를 따로 저장한다(기존 정원의 배열의 범위를 넘는 부분은 자른다). ranges[i]의 값이 0이면 저장하지 않는다.

범위의 시작 위치를 기준으로 정렬한다. 

같은 시작 위치 안에서 최대한 멀리 물을 보낼 수 있는 것을 찾고, tab의 수를 1 누적시킨다.  만약 이전의 최대한 먼 위치보다 멀리 보내지 못하면 나머지 뒷 부분은 채우지 못한다는 뜻으로 -1을 반환시키고, 

 

코드

C++

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int, int>> watering;
        for (int i = 0; i <= n; ++i) {
            if (ranges[i] == 0) continue;
            watering.push_back(make_pair(max(0, i - ranges[i]), min(n, i + ranges[i])));
        }
        
        sort(watering.begin(), watering.end());
        
        int taps = 0, idx = 0, end = 0, nextEnd = 0;
        
        while (idx < watering.size() && end < n) {
            while (idx < watering.size() && watering[idx].first <= end) {
                nextEnd = max(nextEnd, watering[idx].second);
                ++idx;
            }
            if (nextEnd <= end) return -1;
            end = nextEnd;
            ++taps;
        }
        return (end >= n) ? taps : -1;
    }
};