1
$\begingroup$

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.

  • 0
    Well if you could then making some other basic assumptions too $k$ fire extinguishers would suffice for a fire of total length $km$.2012-08-16

1 Answers 1

2

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 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.

Obviously, after deciding where one fireman is, we still want to solve the remaining problem optimally, so we continue in the same manner.

That's the solution you get from this code.

  • 0
    "for each fire the optimal solution must.." doesn't make sense to me. I'll try to rephrase your comment correctly: If you take an optimal solution, you can turn it into the greedy solution by shiting only. Since shifting does not change the number of firemen, we deduce that the greedy solution has exactly as many firemen as some optimal solution. Therefore, the greedy solution is optimal too.2012-08-15