rr459595's blog

Greedy approach proof
By rr459595, history, 5 years ago, In English

I solved this problem on hackerrank ( https://www.hackerrank.com/contests/dcl2k15/challenges/mice-v1 ) based on greedy approach. I am not able to understand the proof of the greedy approach.

The proof says max( |a1-b1| , |a2-b2| ) <= max( |a1-b2|, |a2-b1| ) for a1<a2 and b1<b2. Can someone help me in proving the inequality?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How can you say you solved it if you don't understand the proof?

You can assume without loss of generality, that $$$a_1 \le b_1$$$. Then you can check three cases: either $$$a_2 \le b_1$$$ or $$$b_1 \le a_2 \le b_2$$$ or $$$b_2 \le a_2$$$. Prove the inequality for all three cases separately. It should be pretty mechanical.

→ Reply