Building Bridges

Statement

Two cities are to be connected via $n$ number of bridges over a river. The north bank of the river belongs to city $A$, while the south bank to city $B$. 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 ${i^{th}}$ point of city $A$ is connected to the ${i^{th}}$ point of city $B$, keeping in view that no two bridges overlap each other? While building bridges, you can only connect the $A[i^{th}]$ bridge on the north bank with the $B[i^{th}]$ point on the south bank.

For example, we have two arrays:

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

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

One possibility is that we can connect $1$ with $5$ and $2$ with $6$. If we connect $4$ with $3$, then this would overlap both the previous bridges. Hence, only two non-overlapping bridges can be formed in this example.

Constraints:

• $1 \leq n \leq 995$

• $1 \leq$ north.size $\leq n$

• $1 \leq$ south.size $\leq n$

• $1 \leq$ north[i], south[i] $\leq 10^5$

Examples