This script works but keeps timing out with longer inputs. How can I improve its speed? [Ruby]
So, you are generating every possible permutations of the array, which is a O(n!) operation. This is huge.

I think this can be done with an O(n²) algorithm. I would do :


create an array containing the pairs, ordered by the first value
create another one containing the pairs, ordered by the second value
create a third array containing, for each index of the first array, the index in the second array where we can find the corresponding value.
find every subset of this third array whose values are in ascending order.


The result is the length of the biggest subset.

Example

first array | second array | third array
------------+--------------+------------
15,176      | 102,6        | 7
39,47       | 123,37       | 3
44,168      | 72,43        | 6
65,97       | 39,47        | 4
72,43       | 65,97        | 2
90,163      | 90,163       | 5
102,6       | 44,168       | 0
123,37      | 15,176       | 1
191,189     | 191,189      | 8


The ascending subsets are :


7 8
3 6 8
3 4 5 8
6 8
4 5 8
2 5 8
5 8
0 1 8
1 8
8


The biggest subset is (3 4 5 8), and its size is 4.

Complexity

The sorts can be done with O(n log n)
The creation of the third array is O(n²)
To find the subset, I think we can do that with O(n²) (I'm not sure about that)

So, the whole thing should be O(n²).

The algorithm for finding the ascending subsets is not trivial. I'm sure it will be fun to implement !