# Finding linear order of set maximising number of consecuitive subsets

I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the one I present it here (permutations, strings, trees, ...)?

Let $$S$$ be a discrete, finite set. Let $$S_1, S_2, \ldots, S_k$$ be subsets of $$S$$. Consider a linear order $$R$$ on $$S$$. We say $$R$$ represents $$S_i$$ if the elements of $$S_i$$ appear consecutively in $$R$$.

Given $$S$$ and $$S_1, \ldots, S_k$$, find a linear order $$R$$ of $$S$$ that maximises the number of subsets $$S_i$$ it represents.

I can solve the problem when $$R$$ can represent all subsets (with PQ-trees).

## Example

Let $$S = \{1, 2, 3, 4, 5\}$$ and $$S_1 = \{1, 2, 3\}$$, $$S_2 = \{3, 5\}$$, $$S_3 = \{2, 4\}$$, $$S_4 = \{1, 5\}$$.

For $$R = (2, 1, 3, 5, 4)$$, we have that $$S_1$$ and $$S_2$$ are consecuitive in $$R$$ but $$S_3$$ and $$S_4$$ are not.

For $$R' = (4, 2, 1, 3, 5)$$, we have that $$S_1$$, $$S_2$$, and $$S_3$$ are consecuitive in $$R'$$ but $$S_4$$ is not. Note that we can actually not do better than $$R'$$, which is good for three of the four subsets.