Building Bridges

Let's solve the Building Bridges problem using Dynamic Programming.

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] ...

Access this course and 1400+ top-rated courses and projects.