Building bridges is a classical computer science problem known for its relation to both dynamic programming and graph theory. The problem can be explained using a metaphor of building non-crossing bridges between pairs of points on two parallel lines. Its solution involves computing the Longest Increasing Subsequence (LIS), a well-known problem in the realm of computer science. In this article, we'll delve into the technical details and explore how the LIS can be leveraged to solve the building bridges problem.

Problem Definition

The building bridges problem is typically presented as follows:

• You are given two parallel horizontal lines. On each line, there are several points.
• Each point on the top line has a corresponding point on the bottom line, given as pairs. These pairs represent potential bridges.
• The goal is to construct as many non-overlapping bridges as possible.

This problem can be visualized by imagining these points and their connections as points on a graph. The core challenge is to ensure that none of the bridges (connections) cross each other.

Connection to Longest Increasing Subsequence

The key insight for solving the building bridges problem is to recognize that it's fundamentally about finding a Longest Increasing Subsequence. First, you’ll need to sort the pairs of points based on one of the lines (say, the top line). Once sorted by one line, the problem reduces to finding the LIS of the second line’s coordinates.

Steps to Solve the Problem

1. Pair Representation: Each pair represents a bridge, e.g., (x1, y1) where x1 is a point on the top line, and y1 is a point on the bottom line.
2. Sort Pairs: Sort the pairs by the first element (x1). If two pairs have the same first element, sort by the second element (y1).
3. Find LIS: Apply LIS on the sequence of the second elements after sorting.

• Sorting Pairs: Sorting the pairs takes $O(n \log n)$ time.
• Calculating LIS: The traditional approach for LIS runs in $O(n^2)$ time, but with the use of advanced data structures such as Fenwick trees or binary indexed trees, it can be reduced to $O(n \log n)$.
• Given pairs: [(6, 2), (4, 3), (7, 4), (9, 5)]
  • Sorted pairs: [(4, 3), (6, 2), (7, 4), (9, 5)]