reference : http://kaustubh-karkare.blogspot.in/2012/09/directi-selection.html
spoj link
http://www.spoj.com/problems/BRIDGE/
reference
Given the coordinates of N pairs of cities, each pair containing cities on two opposite sides of a river, we need to make bridges between the pairs. What is the maximum number of non-overlapping bridges that can be built? I had seen this question somewhere not to long ago, so I was able to give an O(nlgn) solution in which we sort according to one coordinate (X) and then perform an LIS on the other (Y). I gave the answer instantly,
spoj link
http://www.spoj.com/problems/BRIDGE/
reference
Given the coordinates of N pairs of cities, each pair containing cities on two opposite sides of a river, we need to make bridges between the pairs. What is the maximum number of non-overlapping bridges that can be built? I had seen this question somewhere not to long ago, so I was able to give an O(nlgn) solution in which we sort according to one coordinate (X) and then perform an LIS on the other (Y). I gave the answer instantly,
No comments:
Post a Comment