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.