Skip to interview prep
Apexed

373. Cities on the north bank of a river are paired with cities on the south bank. Build as many bridges between pairs as possible without any two crossing.

MediumDynamic programming

Technical
Show model answer

Two bridges (n1, s1) and (n2, s2) do not cross exactly when n1 < n2 and s1 < s2. Sort the pairs by north coordinate (breaking ties by south coordinate ascending if bridges may share an endpoint, or descending if they may not), then the answer is the longest increasing subsequence of the south coordinates.

With the patience-sorting LIS, the whole algorithm is O(n log n) time and O(n) space; the plain LIS DP gives O(n²). This 'sort by one key, LIS on the other' reduction also solves Russian dolls, the circus tower and longest chain of pairs.

Cities on the north bank of a river are paired with cities on the south bank. Build as many bridges between pairs as possible without any two crossing. — Data s