Building Bridges Problem - Solution Using LIS

Solve a real interview problem based on the concept of Longest Increasing Subsequence.

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 ith{i^{th}} point of the first array must be connected to ith{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., ith{i^{th}} point in the 1st{1^{st}} sequence is paired with ith{i^{th}} point in the 2nd{2^{nd}} sequence. Then, we sort the points with respect to the 1st{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.

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