Building bridges problem - how to apply longest increasing subsequence?

Question

The building bridges problem is stated as follows:

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.

I have heard that this problem is related to the longest increasing subsequence problem, but I don't see how to use it here. For example, if we're given the pairs

2  5  8  10
6  4  1  2

Then which sequence do we consider for LIS?

Thanks!

Extrajudicial

I don't think problem is as commonly-known as you might suspect... can you describe it in more detail? – Abott

Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank – Extrajudicial

@pranay- Are the cities on the bank sorted by x coordinate? Or are they in random order? – Abott

@templatetypedef: they may be in random order or may be sorted – Extrajudicial

Isn't it clear that 2 5 8 10 is the longest between the two? – Votyak

I think your problem statement is "incorrect", if you take a look at: geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis lets take one step back, say you have n buildings at northern bank, and another n buildings at the southern bank, there is a mapping because northern city to southern city, so, you can image that actually one of the bank's city is considered "sorted" – Chromatogram

Answer 1

To build up to how you'd use the longest increasing subsequence algorithm to solve this problem, let's start off with some intuition and then build up to a solution. Since you can only build bridges between cities at matching indices, you can think of the set of bridges that you end up building as the largest set of pairs you can find that don't contain any crossing. So under what circumstance would you have a crossing?

Let's see when this can happen. Suppose that we sort all of the bridges built by their first city. If two bridges cross, then we must have that there is some bridge (a_i, b_i) such that for some other bridge (a_j, b_j) one of the following holds:

• a_i < a_j and b_i > b_j
• a_i > a_j and b_i < b_j

This first case says that there is a bridge whose top city is further to the right than the start of our bridge and whose bottom city is further to the left than the end of our bridge, and the second case handles the opposite case.

Given that this property needs to hold, we need to ensure that for every set of bridges, we have that exactly one of the two following properties holds for any pair of bridges (a_i, b_i), (a_j, b_j): either

• a_i ≤ a_j and b_i ≤ b_j

or

• a_i ≥ a_j and b_i ≥ b_j

In other words, if we were to sort the bridges by their first coordinate, the set of second coordinates would always be increasing. Similarly, if we were to sort the bridges by their second coordiante, the first coordinate would always be increasing.

The property that we've just defined defines a partial ordering ≤_both on the set of bridges, where we say that (a_i, b_i) ≤_both (a_j, b_j) if a_i ≤ a_j and b_i ≤ b_j. Notice that this is not a total ordering - for example, (1, 2) is incomparable with (2, 1) - but it is a partial ordering because it is reflexive, antisymmetric, and transitive.

Given this, the goal of the problem is to find the largest set of elements that we can that can be totally ordered by this relationship, since if we have a set containing two incomparable elements those elements must necessarily represent crossing bridges. In other words, we want to find the longest chain in the partial order. One way to do this is to, in O(n²) time, compare each element to each other element and see which elements can be ordered by ≤_both. This produces a directed acyclic graph, where the pair (a_i, b_i) has an edge to (a_j, b_j) iff (a_i, b_i) ≤_both (a_j, b_j). Once we have this directed acyclic graph, we can then find the longest path in the graph to find the largest set of elements that are call comparable by ≤_both, which then gives the solution to the problem. The overall runtime is thus O(n²).

However, we can do substantially better than this. The problem with the above algorithm is that we can't easily tell how the elements compare against one another, so we have to explicitly compare each city against each other city.

2  5  8 10
6  4  1  2 

Let's sort the cities by the bottom row:

8 10  5  2
1  2  4  6

Now, here's the really cool observation. If we have the elements sorted by their bottom row, then we can tell if two pairs are orderable by ≤_both by looking at their positions in the top row. If the first pair is to the left of the second pair, we immediately know that the second elements of the first pair is less than the second element of the second pair, since we've sorted them by the second coordinate. We then have that the pair of elements can be built together iff the first element of the first pair is less than the first element of the second pair. Consequently, if we want to find a set of bridges that can be built together, we're looking for an increasing subsequence of the top row, 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. Since we can sort the pairs by their second field in O(n log n) and find the longest increasing subsequence in O(n log n), this is an O(n log n) solution to the problem!

Whew! Hope that this answer explains things in detail!

Abott

Great intuition about the dag – Evangelineevangelism

Its been more than 3yrs since you wrote this answer.. But still very helpful.. :D – Liebig

@mohit Can you elaborate? Which two sequences would you be using? – Abott

Answer 2

First consider the pairs: (2,6), (5, 4), (8, 1), (10, 2), sort it according to the first element of the pairs (in this case are already sorted) and compute the list on the second element of the pairs, thus compute the LIS on 6 4 1 2, that is 1 2. Therefore the non overlapping lines you are looking for are (8, 1) and (10, 2).

Evangelineevangelism

you're welcome ;)..if you haven't done it yet give me a +1 please ;D – Evangelineevangelism

Nice solution. +1 from me also. :) – Dropping

yeah from me also! better than accepted one! short and sweet – Centric

Answer 3

Here is an Java implementation of the problem.

    package DP;

    import java.util.Arrays;
    import java.util.Comparator;

    public class BuildingBridges {

        public static void main(String[] args) {
            Pair[] A = new Pair[7];
            A[0] = new Pair(22,4);
            A[1] = new Pair(2,6);
            A[2] = new Pair(10,3);
            A[3] = new Pair(15,12);
            A[4] = new Pair(9,8);
            A[5] = new Pair(17,17);
            A[6] = new Pair(4,2);

            System.out.println(lis(A));
        }

        public static int lis(Pair[] A){
            Arrays.sort(A, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.x - o2.x;
                }
            });

            int n = A.length;
            int max = 0;
            int[] dp = new int[n];
            Arrays.fill(dp, 1);

            for(int i=1; i<n; i++){
                for(int j=0; j<i; j++){
                    if(A[i].y > A[j].y){
                        dp[i] = Math.max(dp[i], dp[j]+1);
                    }
                }
                max = Math.max(max, dp[i]);
            }

            return max;
        }

        public static class Pair{
            int x, y;
            public Pair(int x_, int y_){
                x = x_;
                y = y_;
            }
        }

    }

Monti

Answer 4

This is a dynamic programming problem, which can be modelled even as a Longest Subsequence Problem. Consider the coordinates of the cities to the north of the river be a1,a2,a3..aN. Now find the corresponding cities in the south of the river and mark them as a1,a2,a3..aN as well. The solution to the problem will then be the longest common subsequence of the strings formed by the aI's in the north and south of the river.

Pleuropneumonia

Answer 5

This is a working code in c++ for the above problem.

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct pairs{
int x;
int y;  
};

bool myf(struct pairs p1,struct pairs p2){
return p1.x<p2.x;   
}

int lis(struct pairs a[],int n){
sort(a,a+n,myf);

int lis[n];

for(int i=0;i<n;i++)
    lis[i]=1;

for(int i=1;i<n;i++){

    for(int j=0;j<i;j++){
        if((a[j].y<a[i].y)&&(lis[i]<lis[j]+1))
            lis[i]=lis[j]+1;
    }
}

int max=lis[0];

for(int i=1;i<n;i++){
    if(max<lis[i])
        max=lis[i]; 
}

return max;
}

int main()
{
struct pairs arr[100];
int n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i].x>>arr[i].y;    
}

int max=lis(arr,n);
cout<<max<<"\n";

return 0;
}

Carapace

But with no explanation or comments to explain why it is working. – Amoreta

Answer 6

Sort one list and find LIS in other.C++ code->

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b){
    return a.first<b.first;
}

int bridges(vector<pair<int,int> > connect){
    int i, j, n=connect.size();
    sort(connect.begin(),connect.end(),cmp);
    vector<int> lis(n,1);
    int m=0;
    for(i=0;i<n;i++){
        for(j=i-1;j>=0;j--){
            if(connect[i].second>connect[i].first)lis[i]=max(lis[i],lis[j]+1);
        }
        m=max(m,lis[i]);
    }
    return m;
}

int main(){
    int n, i;
    cin >> n;
    vector<pair<int,int> > a(n);
    for(i=0;i<n;i++)cin >> a[i].first >> a[i].second;
    cout << bridges(a) <<endl;
    return 0;
}

Micronutrient

Answer 7

This is Building bridge problem with no crossing allowed and can be solved using below three steps.

• Sort the array in increasing order of first value of the pair. If two first values are the same, for example we have (3, 6) and (3, 5), then consider the second value. So in this example (3, 5) will come before (3, 6).
• Find the LIS (Longest Increasing Subsequence) of the sorted array according to second values.
• Output is length of LIS array

Let us take an example:

Input: [(8, 1), (1, 2), (4, 3), (3, 4), (2, 6), (6, 7), (7, 8), (5, 5)]

Step 1: [(1, 2), (2, 6), (3, 4), (4, 3), (5, 5), (6, 7), (7, 8), (8, 1)]

Step 2: LIS of [2, 6, 4, 3, 5, 7, 8, 1] = [2, 4, 5, 7, 8]

Step 3: Output is len([2, 4, 5, 7, 8]) = 5

Prolong