Constructing Bridges

Problem:
A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.
Construct as many Non-Crossing Bridges as possible.
Input:
Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)
Output:
(1,1) (3,2) (4,3) (6,4) (7,5)

Solution:
Its an Longest Increasing Sub-Sequence Dynamic programming Problem with O(N log N) solution.

Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
Pairs >> (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Sort the pairs based on Lower Bank Cities as Below:
Above Bank >> 1 3 4 6 7 2 5
Below Bank >> 1 2 3 4 5 6 7

Now the Problem reduces to finding the LIS from the Cities in Above Bank >> 1 3 4 6 7 2 5
which is 1 3 4 6 7

So, the Output with corresponding Lower Bank Cities will be
(1,1) (3,2) (4,3) (6,4) (7,5)

EDIT:
If we have the elements sorted by their Below Bank, then we can tell if two pairs are orderable by <=, by just looking at their positions in the Above Bank.
If the first pair(1,1) is to the left of the second pair(3,2), we immediately know that the second elements of the first pair(1) is less than the second element of the second pair(2), since we've sorted them by the second coordinate.
We then have this pair of elements can have Bridge built together if and only if the first element of the first pair(1) is less than the first element of the second pair(3).

Consequently, if we want to find a set of Bridges that can be built together, we're looking for an Increasing Sub-Sequence of the Cities in Above Bank, since in that case both the first and second elements of the pairs are increasing as we move from the left to the right.

Finding the longest increasing subsequence then solves this problem.

Complexity:
Sort the pairs by their Below Bank = O(N log N)
Find the LIS in O(N log N)
So, this is an O(N log N) solution.