A question on linear extensions of partial orders
If every sequence has length 3, the problem is known as Betweenness. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard. 

The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing, 8(1):111—114, Feb. 1979.

[2] B. Chor and M. Sudan. A geometric approach to betweenness, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.

Edits: clarified that the decision version of the problem is NP-hard.