Building bridges

[nuzzle]

Thefore, maximum number of overlapping bridges are 2.

Thank you, I get it now.

I think you've come up with a nice solution strategy. First sorting the bridges according to "from" and then finding the longest increasing subsequence among the "to". That would correspond to the largest number of non-intersecting bridges.

The sorting is O(N*logN) but it looks like you have an O(N^2) algorithm for the subsequence part. According to this link, O(N*logN) is possible for the latter also,

http://en.wikipedia.org/wiki/Longest...ng_subsequence

That means a solution with a total complexity of O(N*logN) is possible for this problem.