So Long......

Wow.. That is the first time i write a long article in english.It took a lot more time that i expected. At first i thought that it will only take 30 minutes, but it takes 2 hours! Writing an article like that make me seriously studying about interval covering! It was very effective! (P*kem*n reference btw). Should i make an article everytime i half-understand a topic in programming?

Greedy - Interval Covering

Interval Covering is one of the classical greedy problem.
The problem is, given an area and some cover, cover the area with minimal numbers of covers. My sentence is probably hard to understand, so here's some example.

1. UVa 12321 - Gas Stations
There are G numbers of gas stations operating over a road with length L. Each gas station have an area of influence where it is able to sell fuel. Find out maximum number of gas stations that can be closed while the remaining gas stations still covering the whole road.

2. Imagine there's a neighborhood. You want to build a number of hospital to provide medical services to the people. There are a few vacant lot in the neighborhood where you can build a hospital, and each hospital only can provide services to people residing in some distance from the hospital. Building a hospital cost money, so you want to build as few as possible hospital while still providing medical services to the whole neighborhood. How many and where you have to build hospitals?

So, how should you approach this kind of problem?
The first thing i thought is to pick the covers according to descending order based on its radius/coverage/length of road it can cover while there are still area uncovered. However, this approach is wrong. Why?

Example :
Suppose there are a road of length 20. The list of gas stations is located at length 5 with 5 radius, at length 15 with 5 radius, and at length 10 with 9 radius.

If you use this approach, it will pick all of the covers, because when it pick the third cover, there are still uncovered road at length 1 and 20. The right answer is two, using the first cover and the second cover, ignoring the last cover.

The right approach is, to sort the covers based on increased left endpoint/left most point the cover can reach, and if the left endpoint is same based on decreasing right endpoint. Then iteratively scan the interval one by one and take the one that reach as far as possible to the right, yet still form contingous coverage.

Using the example above, the sorted gas stations will be :
                      Location Radius Leftendpoint Rightendpoint
First Cover           5            5             0                    10
Third Cover         10           9             1                    19
Second Cover     15           5            10                   20

First, the algorithm will pick the first cover (since there are no cover starting at 0), set the current end to first cover right endpoint, then select the remaining cover that start before or at the current end and reach as far right as possible, and that is the second cover (19 vs 20). With only those two covers, the whole recieve coverage.

Here are the general pseudo-code for Interval Covering problem :

while (currently cover processed is not the last cover) {
     if (the current cover left endpoint can't connect) stop;
     for (all cover which can connect) pick the one with largest right endpoint;
     increase the count of cover taken;
     current end point=taken cover right endpoint;
     if (current end point larger or the same with the area length) stop;
}
if (current end point did not reach area length) return that we can't cover the whole area;
else return the number of cover taken;

That is my understanding of Interval Covering problem, feel free to point out mistakes in my post or asking questions.