Bridge Problem

Consider a river. There are n cities on both the banks of the river. A city from a bank is connected to one city from other bank through bridge.
No two cities from a bank can be connected to the same city on the other side.

As clear from the figure that some of the bridges are crossing each other. So the question is to select maximum number of bridges so that none of the selected bridge is crossing each other.

According to figure , we have 6 bridges which are connecting various cities .The highlighted bridges are not crossing each other and this is
the maximum number of bridges possible. So the output for above example is 4.

So you have to answer the maximum number of non crossing bridges.

Solution:

class BridgeProblem{
static int find(String []arr){
if(arr == null || arr.length == 0)
return -1;

int prev, count = 0;
String []temp = arr[0].split("#");
prev = Integer.parseInt(temp[1]);
count++;
 
           for(int i = 1; i < arr.length; i++){
temp = arr[i].split("#");
int tmp = Integer.parseInt(temp[1]);
if(prev < tmp)
count++;
prev = tmp;
}
return count;
}

public static void main(String... args){
String[] arr = { "1#2", "2#4", "3#1", "4#5", "5#3", "6#6"};
int count = find(arr);
System.out.println(count);
}
}