Building Bridges Problem - Solution Using LIS

Problem statement

You are given two arrays of numbers that denote the endpoints of bridges. What is the maximum number of bridges that can be built if ${i^{th}}$ point of the first array must be connected to ${i^{th}}$ point of the second array and two bridges cannot overlap each other?

Solution: Longest Increasing Subsequence approach

In this problem, we will use the concept of LIS. Two bridges will not overlap with each other if both their endpoints are either in non-increasing or non-decreasing order. To find the solution, we will first pair the endpoints, i.e., ${i^{th}}$ point in the ${1^{st}}$ sequence is paired with ${i^{th}}$ point in the ${2^{nd}}$ sequence. Then, we sort the points with respect to the ${1^{st}}$ point in the pair and apply LIS on the second point of the pair.

Let us take the following example:

Consider the pairs (2,6), (5, 4), (8, 1), (10, 2). Sort them according to the first element of the pairs (in this case, they are already sorted) and compute the LIS on the second element of the pairs (6, 4, 1, 2) that is 1, 2. Therefore the non-overlapping bridges we are looking for are (8, 1) and (10, 2).

Let us now move to the implementation of this solution.