In this tutorial we shall solve building bridges problem with help of DP. This is a classical DP problem.
Problem statement:
Given a river, you need to build a bridge across the river in such a way that only he pair given can form a bridge, and no bridges should be crossing each other.
Example, given the points [1, 2] [5, 4] [8, 10], the bridges can be formed as below:

Below bridges are invalid

The above bridges are invalid because the bridge [10, 6] is crossing [8, 10].
The top is north co-ordinate; bottom is south co-ordinate.
Hence according to the given question, you are given pair and you need to build maximum number of bridges by satisfying the above condition.
We are going to solve this problem with the help of DP and longest common subsequence.
This problem can be solved by given steps :
1. Sort the south co-ordinate in ascending order.
2. Find out the longest increasing subsequence for north co-ordinates
3. Join the bridges in Longest Increasing Subsequence.
Example:
Consider the co-ordinates as below:

Step 1: Sort according to south co-ordinates

Step 2: Find longest increasing subsequence
Here the sorted order is the longest increasing subsequence.

There is a small change when you compare to original Longest Increasing Subsequence algorithm.
i.e. in original algorithm, we only choose the element if the next element is greater. But here we also choose if the element is equal also.