Problem

Problem ID: 1326

Title: Minimum Number of Taps to Open to Water a Garden

Difficulty: Hard

Description:

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.

Thoughts

This is quite a tricky problem as it does not use the definition of an interval. Intervals (i, j) and (j+1, k) do not cover the entire range from i to k.

The key to solving this question is to identify that it is a greedy problem. A model I like to use is to ask myself, at point i, if I choose the interval that contains i and ends the latest, will the answer be wrong when I process the intervals beyond i?

Implementation

O(nlog(n)) solution

General Idea: Similar to LC 56: merge interval questions, we would sort the ranges from by the start of intervals.

Handling edge case: for ranges=0 we would artificially set the range to (-1,-1) as it would not contribute to the intervals.

class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<pair<int,int>> intervals(ranges.size());
for (int i = 0; i < ranges.size(); i++) {
if (ranges[i] == 0) {
// tap will not be able cover its own location so shift it to -1
intervals[i] = make_pair(-1, -1);
} else {
intervals[i] = make_pair(i-ranges[i], i+ranges[i]);
}
}
sort(intervals.begin(), intervals.end());
int next_uncovered;
int count = 0;
int curr_interval = 0;
int last_covered = -1;

for (int i = 0; i < intervals.size(); i++) {
if (i < last_covered) continue;
if (i == intervals.size() -1 && i <= last_covered) break;
while (curr_interval < intervals.size()) {
int start = intervals[curr_interval].first;
int end = intervals[curr_interval].second;
if (start > i) break;
last_covered = max(last_covered, end);
curr_interval++;
}
if (last_covered < i) return -1;
count++;
}
return count;
}
};