Last Updated: 12 Nov, 2021
Connecting Ropes
Hard
Asked in companies
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.
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
Approaches
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.
Approach :
- In the previous approach, we were finding the longest increasing subsequence among the south coordinates in O(N^2).
- Here, we will find the longest increasing subsequence in O(N*logN).
- We maintain an array ‘dp’ with size ‘N+1’ initialised to ‘INF’.
- Now, for every element ‘x’ , we check in array ‘dp’ the lower bound index of the element ‘x’.
- This is because the elements before this index are in increasing order and element ‘x’ can be added at the end of this subsequence.
- We update our answer as the maximum of lower bound index of each element ‘x’.
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+1’ initialized to ‘INF’.
- Run a for loop from ‘i=0’ to ‘i=N-1’.
- Lower bound on the index on array ‘dp’ having ‘dp[idx]’ just greater than or equal to ‘arr[i].south’.
- Update the value at ‘dp[idx]’ with ‘arr[i].south’.
- Update ‘ans’ as the maximum of ‘ans’ and ‘idx+1’.
- Return ‘ans’ as the final result.
Similar problems