CareerCup

Its an Longest Increasing Sub-Sequence Dynamic programming Problem with O(N log N) solution.

Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
Pairs >> (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Sort the pairs based on Lower Bank Cities as Below:
Above Bank >> 1 3 4 6 7 2 5
Below Bank >> 1 2 3 4 5 6 7

Now the Problem reduces to finding the LIS from the Cities in Above Bank >> 1 3 4 6 7 2 5
which is 1 3 4 6 7

So, the Output with corresponding Lower Bank Cities will be
(1,1) (3,2) (4,3) (6,4) (7,5)

EDIT:
If we have the elements sorted by their Below Bank, then we can tell if two pairs are orderable by <=, by just looking at their positions in the Above Bank.
If the first pair(1,1) is to the left of the second pair(3,2), we immediately know that the second elements of the first pair(1) is less than the second element of the second pair(2), since we've sorted them by the second coordinate.
We then have this pair of elements can have Bridge built together if and only if the first element of the first pair(1) is less than the first element of the second pair(3).

Consequently, if we want to find a set of Bridges that can be built together, we're looking for an Increasing Sub-Sequence of the Cities in Above Bank, 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.

Complexity:
Sort the pairs by their Below Bank = O(N log N)
Find the LIS in O(N log N)
So, this is an O(N log N) solution.

import java.util.HashMap;
import java.util.Map;


/**
* @author shashi
*
*Constructing Bridges:
A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.
Construct as many Non-Crossing Bridges as possible.
Input:
Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)
Output:
(1,1) (3,2) (4,3) (6,4) (7,5)
*/
public class RiverBridge {

public static void main(String []args)
{
//get the above and below banks
int aboveBank[]={7 ,4, 3, 6, 2, 1, 5};
int belowBank[]={ 5, 3, 2, 4, 6, 1, 7};

//now create a Map for storing Pairs
Map<Integer, Integer> myMap=new HashMap<Integer, Integer>();
//base condition
if(aboveBank.length !=belowBank.length)
{
//River flow is not correct way
System.out.print("Your river is not flowing in correct way");
}
//if not
for(int i=0;i<aboveBank.length-1;i++)//you can also use below.length
{
if(aboveBank[i]>=belowBank[i])
{
//pair for bridge is founded so add to map
myMap.put(aboveBank[i], belowBank[i]);
}
}
//now print map elements
for(Map.Entry<Integer, Integer> entry:myMap.entrySet())
{
int key=entry.getKey();
int val=entry.getValue();
System.out.print("("+key+","+val+")"+" " );
}

}
}

Anyone can explain me how its 5?

Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7

Output:
(1,1) (3,2) (4,3) (6,4) (7,5)

How we making bridge here, i think same city should be connected with bridge...

Someone can explain then its good

i am thinking only 3 bridge are possible

(1,1) (4,4) ( 6,6)

or
(3,3),(2,2),(1,1)

package com.ixo.data.dataprocessor;

import java.util.Comparator;
import java.util.List;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.tuple.Pair;

public class BridgeProblem {
	
	public static void PrintMaxBridgeCount(List<Pair<Integer, Integer>> bridgeList) {
		bridgeList.sort(new Comparator<Pair<Integer, Integer>>() {
			@Override
			public int compare(Pair<Integer, Integer> left, Pair<Integer, Integer> right) {
				return left.getLeft() - right.getLeft();
			}
			 
		});
		
		//dp struct
		int[] cmax = new int[bridgeList.size()];
		int[] prevNodes = new int[bridgeList.size()];
		
		for(int n = 0; n < bridgeList.size(); n++) {
			int max = 1;//when no other
			int prevNode = -1;
			Pair<Integer, Integer> nthItem = bridgeList.get(n);
			for (int i = 0; i < n; i++) {
				//CRUX: consider only those items which will include nth item
				//IMP FOR DP
				if (nthItem.getRight() >= bridgeList.get(i).getRight()) {
					if (cmax[i] >= max) {
						max = cmax[i] + 1;
						prevNode = i;
					}
				}
			}
			
			cmax[n] = max;
			prevNodes[n] = prevNode;
		}
		
		System.out.println("max bridges:" + cmax[bridgeList.size()-1]);
		String bridgesToConstruct = StringUtils.join(prevNodes, ",");
		System.out.println("Bridges:" + bridgesToConstruct);
	}
	
	
}

#include<stdio.h>

int main()
{
        int above_bank[]={7,4,3,6,2,1,5};
        int below_bank[]={5,3,2,4,6,1,7};
        int len_a, len_b, i;

        for(len_a=0; above_bank[len_a];len_a++);
        printf("len of a=%d\n",len_a);

        for(len_b=0; above_bank[len_b];len_b++);
        printf("len of b=%d\n",len_b);

        if(len_a != len_b)
        {
                printf("not possible\n");
                return 0;
        }

        for(i=0;i<len_a; i++)
        {
                if(above_bank[i] >= below_bank[i])
                        printf("pair is %d ,%d\n",above_bank[i], below_bank[i]);
        }
        return 0;
}

~

#include<stdio.h>
#include<stdlib.h>

main(int argc ,char *argv[])
{
        int bridges[][2] = {{7,5},{4,3},{3,2},{6,4},{2,6},{1,1},{5,7}};
        int (*arr)[2];
        int i= 0;
        int count = 0;
        arr = bridges;
        while(*arr[i])
        {
        count++;
        i++;
        }
        printf("No of bridges pairs %d\n",count);

        i =0;
        arr = bridges;
        while(*arr[i])
        {
                if(*arr[i] >= arr[i][1])
                        {
                                printf("%d %d\n", *arr[i], arr[i][1]);
                        }
                i++;
        }

}