question
Given N pairs of integers, write an algorithm to sort the pairs so that the first number in each pair is sorted increasingly whle the second number in each pair is sorted decreasingly. The first and second numbers in each pair can be swapped. Sometimes there will be no solution, in that case throw an exception.
Examples:
Input:
Output:
Input:
Output:
Examples:
Input:
1 5
7 1
3 8
5 6
Output:
1 7 <- Swapped
1 5
6 5 <- Swapped
8 3 <- Swapped
Input:
1 5
6 9
Output:
Not Possible Exception
Think of each pair as an interval. Drawing a visual may help a lot.
This question was initially posed on StackOverflow and I've copied the top answer which was very well explained below.
The answerer also included a brief addendum in the original posts' comments:
"Adding an interval is "legal" if it is a sub-interval of the latest interval in a list. Yes, "middle" two items must also overlap, forgot to mention that. About failures: when my algorithm returns failure, it always identifies 3 incompatible intervals. Note that there are only a few ways to order the end-points of 3 intervals, and the two non-trivial and applicable orderings are pictured." - Tom Sirgedas
Thoughts or alternate solution? Let us know in the comments below!
The answerer also included a brief addendum in the original posts' comments:
"Adding an interval is "legal" if it is a sub-interval of the latest interval in a list. Yes, "middle" two items must also overlap, forgot to mention that. About failures: when my algorithm returns failure, it always identifies 3 incompatible intervals. Note that there are only a few ways to order the end-points of 3 intervals, and the two non-trivial and applicable orderings are pictured." - Tom Sirgedas
Thoughts or alternate solution? Let us know in the comments below!