Of course one does not want brute force, but the case count is not as bad as suggested. I think a reasonable upper bound on the number of cases might be (a shift of the) the Padovan Sequence $1,1,1,2,2,3,4,5,7,12,\cdots$ with $p_n=p_{n-2}+p_{n-3}$ which is $O(\theta^n)$ for $\theta\approx 1.3245\cdots$ the unique real root of $t^3-t-1$. This is based on the idea that the hardest case is if the points are alternately in $A,B,A,B,\cdots.$

I will sketch this and give similar bounds. Consider the $n-1$ intervals $I_j=[x_j,x_{j+1}]$ (with the points $x_1 \lt x_2\lt \cdots)$ Then $\Gamma$ is one of the $2^{n-1}$ ways to pick some of those sub-intervals. If $A,B$ are disjoint that falls to $2^{n-3}$ since we can't omit $I_1$ nor $I_{n-1}$ and in fact to $F_{n-2} \lt 2^{n-3}$ since we can't omit two in a row. Of course there is no advantage to keeping all the intervals. We haven't taken into account $A$ and $B.$ Here is why strick alternation is harder than the other cases. Given a run $x_{i+1},\cdots, x_j$ all in $A$ but not $B,$ We can't omit more than one of $I_i,\cdots I_j$ and we should omit one. If there is one of $I_2,\cdots,I_{j-1}$ which is of the maximal length we should omit it. Otherwise the choices are the longest of those (which is second or third longest) or $I_1$ or $I_j$. We may need to see the other choices first before deciding on the second or third longest.) A point in $A \cap B$ splits the problem into two almost disjoint ones.

Assuming the $n$ points $x_1,x_2,x_3,\cdots,x_n$ do alternate $A,B,A,B,\cdots,$ let $c_n$ be the number of possible cases for $\Gamma$ where we assume nothing about the actual values of the $x_i$ except that they increase. Then $c_2=c_3=c_4=1.$ I will now observe that $c_n=c_{n-2}+c_{n-3}$ for $n \ge 5.$

We will have to use the interval $I_1$ . Record this, then shift to considering $x_2,x_3,\cdots,x_{n}$ where the $x_2$ is now considered **universal** , i.e. in $A \cap B,$ If we do not use [x_2,x_3] then we have the $c_{n-2}$ cases for $x+3,x_4,\cdots,x_n$ If we *do* use $[x_2,x_3],$ it is for the benefit of $x_3$ in which case we do not use $[x_3,x_4].$ This gives the $c_{n-3}$ cases for $x_4,x_5,\cdots, x_n.$

Once the members of $A \cup B$ are listed in increasing order we can in $O(n)$ time list for each $x_i$ the closest $x_j \le x_i \le x_k$ with $x_j,x_k \in B$ ($A$ resp.) if $x_i \in A$ ($B$ resp.) I feel that $O(n)$ time might be enough to finish, but I could be wrong.

**LATER** A few more observations:

Every complete interval in $\Gamma$ is of type $AB,ABA,BA$ or $BAB$ where type $ AB$ means one or more points, all from $A$ (in increasing order) followed by one or more all from $B.$ However type $ABA$ means that with one exception every point is from $A$ and the excepional $B$ is not an endpoint.

In particular, if the points happen to be alternately from $A$ and $B$ (the hardest case in my opinion) then $\Gamma$ consists of a subset of the intervals $I_1,\cdots,I_{n-1}$ which never uses three in a row nor skips two subintervals in a row. In other words, looking at how the points are grouped, the number of possibilities is the number of ways to write $n$ as an ordered sum of $2$s and $3$s

If it happens that $I_k$ is longer than $I_{k-1}$ and $I_{k+1}$ combined then we must not use $I_k$ and hence are forced to use both $I_{k-1}$ and $I_{k+1}$

All this could be adapted to the general case.

9more comments