**Problem:**

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.

**My Approach:**

I am sorting the first set and then finding the largest increasing subsequence from second set despite trying all test cases. I am getting wrong answer. Please help if there is something wrong with the approach or any test case i am missing.

Here is the link to the original problem: http://www.spoj.com/problems/BRIDGE/

#include<stdio.h>

#include<iostream>

#include<algorithm>

using namespace std;

struct dj{

int x;

int y;

}a[1000];

inline int myf(dj dj1,dj dj2)

{

return dj1.x<dj2.x;

}

int main()

{

int n,t,L[1000],len;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%d",&a[i].x);

for(int i=0;i<n;i++)

scanf("%d",&a[i].y);

sort(a,a+n,myf);

L[0]=1;

len=1;

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

{

L[i]=1;

for(int j=0;j<i;j++)

{

if((a[i].y>a[j].y)&&(L[i]<L[j]+1))

L[i]=L[j]+1;

}

if(len<L[i])

len=L[i];

}

printf("%d\n",len);

}

return 0;

}