MadeEasy Test Series: Algorithms - Greedy Algorithm

Question

There are n white dots and n black dots. Equally spaced in a line. You want to connect each white dot with some block dot in one to one fashion with a minimum total length of wire.
Consider 2 examples:

 

Greedy algorithm gives optimal solution for

•  Only (i)

   

• Only (ii)

   

• Both (i) and (ii)

   

• None of these

Comments

@ Shubham

how (2,5)=3?

---

@srestha Its the path length between two dots i.e 2 and 5 .

---

ok , hanks :)

Answer 1

Solve for optimal solution without changing the sequence given in 1 and 2.

For optimal, Leftmost black dot should be matched with the leftmost white dot.

Total length of wire for 1st case according to greedy will be

(1,3)=2

(2,5)=3

(4,6)=2

total length=2+3+2=7

Total Length of wire for 2nd case according to greedy will be

(1,3)=2

(2,4)=2

(5,7)=2

(6,8)=2

total length=2+2+2+2=8

So 1st gives optimal.

Comments

sir,why we don't connect (7,8) in fig(i) plzz answer on this??

Answer 2

https://gateoverflow.in/38415/algo-madeeasy-ts-greedy-method-how-to-approach