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.