CODEWITHSUNDEEP
algorithmdynamic-programming
youssef manyalawy
youssef manyalawy

Reputation: 85

Connect bridges without crossing - dynamic programming algorithms design

Considering a 2-D map with a horizontal river passing through its centre. There are n cities on the northern bank with x-coordinates a(1) ... a(n) and n cities on the southern bank with x-coordinates b(1) ... b(n). I want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, I can only connect city i on the northern bank to city i on the southern bank. How can I solve this using dynamic programmingVisualization of problem?

Upvotes: 1

Views: 322

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65508

Two lines i and j cross if and only if a(i) < a(j) and b(i) > b(j) or a(i) > a(j) and b(i) < b(j). Looking at the lines in a solution sorted by a value, then, there are no crossings if and only if the corresponding b values are increasing. Therefore we should sort the (a, b) pairs by a and compute a longest increasing subsequence on b.

Upvotes: 1

Related Questions