First, we'll prove that there is an optimal solution, which only has connected subsets. Let $A_1,A_2,\cdots A_k$ be optimal. Define $B_i = \{x: min(A_i) \leq x \leq max(A_i)\}$, a.k.а the set that contains all elements between the minimum and maximum of $A_i$. Now, the sets $B_1,B_2,\cdots B_k$ are also a valid solution, because the intersection of each two of them is non empty and closed, and there are no repeating subsets, because if $min(A_i) = min(A_j)$ and $max(A_i) = max(A_j)$ for some $i \neq j$, then $A_i \cap A_j$ is not closed, since at least one of the two sets is not closed. Since the intersection of each two of the intervals is non empty, we have that they have a common interval, a.k.a. a common element. Let that element be $p$. We have $p(n+1-p)$ intervals that contain $p$. The maximum is reached when $p = \lfloor (n+1)/2 \rfloor$, so the answer is $k = {\lfloor (n+1)/2 \rfloor}{\lceil (n+1)/2 \rceil} = \lfloor \frac{(n+1)^2}{4} \rfloor$

Remark

topologicalsort wrote: troll problem Yeap, and nobody solved it during the contest. : )))