Longest subsequence such that A[i].x < A[i+1].y
It's easier to change notation.  Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$.  Associate a directed graph $G$ with the array as follows.  The vertices of $G$ are the indices $1\dots n$ of the array.  Vertex $i$ is connected to vertex $j\ $ if both conditions $i&lt;j$ and $A[i].x &lt; A[j].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$.
Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.