排序数字对的算法

Question

我遇到了一个问题,我需要一些来自SO的聪明人的帮助.我有N对无符号整数.我需要对它们进行排序.对的结束向量应该按每对中的第一个数字非减少地排序,并且每对中的第二个数字不增加.每对可以具有彼此交换的第一和第二元素.有时候没有解决方案,所以我需要抛出异常.

例:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^没有交换对,就不可能构建解决方案.所以我们交换对(7,1),(3,8)和(5,6)并构建结果.要么

in pairs:
1 5
6 9

out:
not possible

另一个显示"排序对"的示例不是解决方案.

in pairs:
1 4
2 5
out pairs:
1 4
5 2

谢谢

Answer 1

O(n log n)解决方案