# how to prove optimality of this greedy algo

I need some suggestions on how to prove the below greedy algorithm is optimal.

Problem: There are $n$ fires on a road. Each fire $i$ is given as an interval where it starts and ends $[s(i), f(i)]$. An extinguisher can cover a fire of length $m$. Find the minimum number of extinguishers to put out all fires.

Algo:

c = 0 # the count of needed extinguishers
L = 0 # the last point where fire is put out
for i=1 to n:
if (s(i) < L) then
s(i) = L
end if
x = (f(i) - s(i))/m # number of extinguishers needed for fire i
c += x # update the total count
L = f(i) + x*m
end for

For the proof of optimality, I think I have to prove that the size of an optimal solution is at most equal to the size of the greedy solution. But how can I exactly prove that? The optimal solution can be a result of any not-necessarily-greedy algorithm. Thank you.

-
Can you use a fire extinguisher on more than one fire, until the extinguisher is finished? –  Mark Bennet Aug 15 '12 at 20:25
@MarkBennet I guess not. But what difference does that make? –  cody Aug 15 '12 at 21:14
Well if you could then making some other basic assumptions too $k$ fire extinguishers would suffice for a fire of total length $km$. –  Mark Bennet Aug 16 '12 at 7:03

Let $i_0$ be such that $s(i_0)$ is minimal (among ${s(i)}_i$). Some fireman must cover $s(i_0)$ so we know that the leftmost fireman covers a segment $[a,b]$ with $a \leq s(i_0)$. On the other side, if you have a fireman covering a segment $[a,a+m]$ with $a<s(i_0)$ then you can move this fireman right to $[s(i_0),s(i_0)+m]$ and you still have a solution with the same number of firemen.
In particular, you can take an optimal solution and shift all firemen covering areas to the left of $s(i_0)$ to the right. Therefore, there is an optimal solution where the leftmost fireman covers $[s(i_0),s(i_0)+m]$. Place a fireman there, remove all the fires or parts of fire he covers and you're left with the same problems, only with less fires, or at least smaller ones.
I assumed that the fires are sorted in increasing order of $s(i)$ and that $x=(f(i)-s(i))/m$ is rounded up. –  user3533 Aug 15 '12 at 21:05