Tuesday, June 14, 2016

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.

No comments:

Post a Comment