Connecting Ropes

Hard
0/120
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
DirectiNewgen Software

Problem statement

Ninja visited his village after a long time. His village is having a river in its center with ‘N’ houses on the northern bank with distinct X-coordinates ‘A[1]’ , A[2]’ , … , ‘A[N]’ and ‘N’ houses on the southern bank with distinct X-coordinates ‘B[1]’ , ‘B[2]’ , …, ‘B[N]’.

Ninja aims to connect as many north-south pairs of houses with ropes as possible such that no ropes cross each other. He will only connect house ‘A[i]’ with house ‘B[i]’.

Given an integer ‘N’ and arrays ‘A’ and ‘B’ representing the coordinates of houses. Find the maximum number of pairs of houses Ninja can connect.

Example : 
N = 3
A = [ 1, 2, 3 ]
B = [ 2, 1, 3 ]

Explanation : 

One of the possible connections can be (1,2) and (3,3).


Another possible connection is (2,1) and (3,3).


Ninja cannot connect all 3 pairs (1,2) , (2,1) and (3,3) as the first 2 pairs cross each other.


So, the maximum connection is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’.

The next line contains ‘N’ integers representing the elements of array ‘A’ which denotes the coordinates of the northern houses.

The next line contains ‘N’ integers representing the elements of array ‘B’ which denotes the coordinates of the southern  houses.
Output format : 
For each test case, output an integer denoting the maximum connections of houses possible.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
2
1 2
1 2
3
1 2 3
3 2 1
Sample Output 1 :
2
1
Explanation Of Sample Input 1 :
For test case 1 we have, 

Both the pairs (1,1) and (2,2) can be connected without any ropes crossing each other. 

So, we output 2.

For test case 2 we have,

Any two pairs of houses will cross with each other.

So, we can only connect 1 of the 3 pairs of houses.

So, we output 1.
Sample Input 2 :
2
4
5 4 7 2 
5 3 4 2 
3
6 4 3 
3 7 5
Sample Output 2 :
3
2
Hint

Think about when two pairs cross each other.

Approaches (2)
Sub-Optimal Approach

 

Approach : 
 

  • We first notice that the pairs (‘n1’,’s1’) and (‘n2’,’s2’) will cross each other if either :
  • ‘n1’ < ‘n2’ and ‘s1’ > ‘s2’
  • ‘n1’ > ‘n2’ and ‘s1’ < ‘s2’
  • To reduce the cases, we just sort the pairs by their north coordinates.
  • So, we only need to take care that there is no pair (‘n1’, ‘n2’) and (‘s1’,’s2’ ) such that ‘s1’ > ‘s2’.
  • So, we need to select the subsequence from the south coordinates which is in strictly increasing order.
  • And to maximize the pair of rope connections, we find the longest increasing subsequence among the south coordinates formed after sorting their respective north coordinates.
  • We find the longest increasing subsequence with the dynamic programming approach.


 

Algorithm : 
 

  • Initialise a variable ‘ans’ = 0.
  • Add the respective coordinates in an array ‘arr’ of pair with their north and south coordinates.
  • Sort the array ‘arr’ with respect to the north coordinates.
  • Maintain an array ‘dp’ of size ‘N’ initialized to 1.
  • Run a for loop from ‘i=0’ to ‘i=N-1’.
    • Run a nested for loop from ‘j=0’ to ‘j=i-1’.
    • If ‘arr[i].south’ > ‘arr[j].south’ :
    • Update ‘dp[i]’ as the maximum of ‘dp[i]’ and ‘dp[j]+1’.
  • Update ‘ans’ as the maximum of ‘ans’ and ‘dp[i]’.
  • Return ‘ans’ as the final result.

 

Time Complexity

O(N^2), where ‘N’ is the length of the array ‘A’.
 

We are running two nested for loops for finding the longest increasing subsequence, so the overall time complexity is O(N^2).

 

Space Complexity

O(N), where ‘N’ is the length of the array ‘A’.
 

We are maintaining an array to store states of longest increasing subsequence. Hence, the overall Space Complexity is O(N).

 

Code Solution
(100% EXP penalty)
Connecting Ropes
Full screen
Console