Building Bridges Problem

There is a river that runs horizontally through an area. There are a set of cities above and below the river. Each city above the river is matched with a city below the river, and you are given this matching as a set of pairs.

You are interested in building a set of bridges across the river to connect the largest number of the matching pairs of cities, but you must do so in a way that no two bridges intersect one another.

Devise an algorithm to solve this problem as efficiently as possible.

http://stackoverflow.com/questions/7288585/building-bridges-problem-how-to-apply-longest-increasing-subsequence