Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 0 down vote accepted

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.

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.

share|improve this answer
    
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
    
So because O is an optimal solution, all fires must be put out. Thus for each fire, the optimal solution must be at least as long as the greedy solution. If it's longer, we can reduce it to the greedy solution by doing the shifting. Do I understand your proof correctly? –  cody Aug 15 '12 at 21:46
    
"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. –  user3533 Aug 15 '12 at 21:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.