Monday, 29 December 2014

Bridge (spoj lis)

reference :
spoj link

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,