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.