**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;
}
