Building Bridges

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:
building_bridges_problem
Below bridges are invalid
building_bridges_problem
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:
building_bridges_problem
Step 1: Sort according to south co-ordinates
building_bridges_problem
Step 2: Find longest increasing subsequence
Here the sorted order is the longest increasing subsequence.
building_bridges_problem
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.
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *