Greedy Algorithm to minimize number of plates used for any array of potholes to
ID: 3702858 • Letter: G
Question
Greedy Algorithm to minimize number of plates used for any array of potholes to cover
Brick roads evidently not being bumpy enough, Little Italy's Mayfield Road has recently developed several potholes. The potholes this year are very bizarre - they are zero-dimensional points which send cars passing over them to a place nobody knows. Unfortunately, the city does not have enough money to hire construction workers, but fortunately, the city does have an enormous reserve supply of 24%24' 2 metal covering plates to prevent cars from entering the underworld. Suppose that you are given an array of the positions of these potholes 3 {81, Sn} where each si represents the distance along the road from the intersection of Euclid and Mayfield to a pothole. Give an algorithm which returns the minimum number of metal plates required to cover all potholes, and prove its correctness. (*)Explanation / Answer
This is the greedy algo given below-
1. Input the distance array A[n], n be number of potholes and set min to infinity.
2. Iterate for i=0,1,2,..,n-1
3. set first_pos=i, set count=1
4. Iterate for j=i+1,..,n-1
5. if((j-first_pos)>24)
6. { first_pos=j
7. count=count+1
8. }
9. end loop
10. set first_pos=i-1, set count2=1
11. Iterate for j=i-2,i-1,..,0 only if (j>=0)
12. if((first_pos-j)>24)
13. { first_pos=j
14. count2=count2+1
15. }
16. end loop
17. if(count+count2 < min) then set min = count+count2
18. end loop
19. return min as answer.
The strategy is- we check each pothole as a pivot or starting point of a metal cover and
try adjusting metal covers as per its dimension to the right first and to the left then,
The two internal loop is for checking number of potholes required in the right side and
left side accordingly when pivot is set to a particular pothole.
For example pothole distances be - { 24,25,26,48,120,121,122,144}
1.if we set pivot at 24 , we need 2 metal covers to cover all 7 potholes situated in right of it
(one covering potholes of distances 24,25,26,48 and another one covering potholes situated at
distances of 120,121,122,144). There are no potholes in right of it.
2.if we set pivot at pothole at distance 25, we will require 2 potholes to cover all potholes in
right of it (one covering potholes of distances 25,26,48 and another one covering potholes situated at
distances of 120,121,122,144). and we will require extra 1 metal cover to cover all potholes in left
of it i.e. the one situated at distance 24. So we need total 3 covers.
We can further calculate all the reqiured metal covers setting pivot each pothole each time, and
the minimum will be the global minimum bumber of covers required.
This is the proof of correctness of the algorithm given.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.