3
$\begingroup$

I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge of the intervals to its left (i.e. preceding it in the given order) contains it.

I am looking for an algorithm to search the optimal ordering, that maximizes the number of visible intervals.

Context: the intervals are spans of text (that all contain a given keyword) and I want to color them using CSS cascading behavior so that all regions are at least partially visible.

Example

A phrase: "The quick brown fox jumps over the lazy dog"

The intervals: ["quick brown fox", "fox", "fox jumps over", "fox jumps over the lazy dog"].

An optimal sorting: ["fox", "quick brown fox", "fox jumps over", "fox jumps over the lazy dog"] (all 4 intervals are "visible")

Non optimal sortings: for instance, any sorting where "fox" is not the first element (so there'd be at most 3 visible intervals).

$\endgroup$
2
  • $\begingroup$ By "on its left" do you mean the intervals that precede the considered one in the order you're looking for? Can you assume that the endpoints of the intervals are distinct? $\endgroup$
    – Steven
    Commented Apr 14, 2020 at 7:37
  • $\begingroup$ @Steven Yes, that's what I meant by "to the left" (though I tend to imagine it in a vertical fashion since this is about painting layers of text). I don't think you can assume that the endpoints are distinct. I've expanded the problem statement with an example. $\endgroup$
    – user119447
    Commented Apr 14, 2020 at 8:08

1 Answer 1

2
$\begingroup$

If no two intervals end at the same point then you can simply sort them in increasing order of their right endpoint, and all of them will be visible.

If more than two intervals can end at the same point, then sort the intervals $[a,b]$ in increasing order of $b$ and break ties in decreasing order of $a$.

Assume w.l.o.g., that there are no identical intervals (you can discard multiple copies of the same interval, since at most one copy will ever be visible). We will show that the above algorithm is optimal with an exchange argument. Suppose that an optimal order $S$ of the intervals places two intervals in a different order than the one computed by the algorithm. Let $[a,b]$ and $[a',b']$ be the first two consecutive intervals in $S$ that are in the "wrong" order, that is:

  • $b>b'$; or
  • $b=b'$ and $a<a'$.

we will show that $[a,b]$ and $[a',b']$ can be swapped without decreasing the number of visible intervals.

If $[a,b]$ is not visible, then swapping $[a',b']$ with $[a,b]$ cannot decrease the number of visible intervals. Therefore we assume that $[a,b]$ is visible. Let $p \in [a,b]$ be the largest point that is not covered by any the intervals preceding $[a,b]$.

If $p \not \in [a',b']$, then swapping $[a',b']$ with $[a,b]$ yields a solution $S'$ in which (i) $[a,b]$ is visible in $S'$, and (ii) if $[a',b']$ is visible in $S$ then it is visible in $S'$. Assume then that $p \in [a',b']$.

If $[a',b']$ is not visible then swapping $[a',b']$ with $[a,b]$ yields a solution in which $[a',b'] \ni p$ is visible (therefore the number of visible intervals cannot decrease). Assume then that $[a',b']$ is visible.

If $[a,b] \supset [a',b']$ then $[a',b']$ would not be visible, therefore we are in the first case ($b>b'$). By the choice of $p$, all the points of the subinterval $(p,b]$ of $[a,b]$ are not visible. Therefore $S$ must contain an interval $[a'',b'']$ that precedes $[a,b]$ and is such that $b'' \ge b$ and $a'' > p$. This cannot happen since $[a'', b'']$ and $[a, b]$ is a pair of intervals in the wrong order which appears before the pair $[a,b]$ and $[a', b']$ in $S$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.