Longest increasing subsequence on pairs
When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i_1,\ldots,i_\ell$ such that
$$
a_{i_1} &lt; \cdots &lt; a_{i_\ell} \\
b_{i_1} &lt; \cdots &lt; b_{i_\ell}
$$
This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.