How do I sort a list of tuples by both elements?

Question

I have a list of tuples, for example [(1800, 3), (4000, 5), (1999, 4), (2000, 1), (2001, 2)]. I need a list of a set length (3, for example) using any combination of these tuples where BOTH elements are sorted in ascending order, like [(2000, 1), (2001, 2), (4000, 5)]. So [(1800, 3), (1999, 4), (2000, 1)] wouldn't work because it's sorted by the first element but not the second. Is it possible to sort a list the way I need?

Answer 1

This is not really a sorting problem; it is a kind of search problem, since you're searching for a subset of the elements which satisfies some criteria.

You can solve it as follows. Sort the list normally, i.e. by first component (using the second component as a tie-breaker); then you are looking for an increasing subsequence in the second component. You can find a longest increasing subsequence using a standard algorithm. If this subsequence is not long enough, then there is no solution (so return None or raise an error); if it is longer than necessary, then simply slice it to the right size.