Statement

Two cities are to be connected via nn number of bridges over a river. The north bank of the river belongs to city AA, while the south bank to city BB. Considering this scenario, suppose we have two arrays, north and south, consisting of positive integers.

Note: north represents the coordinates of bridges on the northern bank of the river, whereas south represents the coordinates of bridges on the southern bank.

What is the maximum number of bridges if the ith{i^{th}} point of city AA is connected to the ith{i^{th}} point of city BB, keeping in view that no two bridges overlap each other? While building bridges, you can only connect the A[ith]A[i^{th}] bridge on the north bank with the B[ith]B[i^{th}] point on the south bank.

For example, we have two arrays:

  1. north=[6,4,2,1]north = [6, 4, 2, 1]

  2. south=[2,3,6,5]south = [2, 3, 6, 5]

One possibility is that we can connect 11 with 55 and 22 with 66. If we connect 44 with 33, then this would overlap both the previous bridges. Hence, only two non-overlapping bridges can be formed in this example.

Constraints:

  • 1n9951 \leq n \leq 995

  • 11 \leq north.size n\leq n

  • 11 \leq south.size n\leq n

  • 11 \leq north[i], south[i] 105\leq 10^5

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.