Let $n\geq 2$ be an integer. Let us call interval a subset $A \subseteq \{1,2,\ldots,n\}$ for which integers $1\leq a < b\leq n$ do exist, such that $A = \{a,a+1,\ldots,b-1,b\}$. Let a family $\mathcal{A}$ of subsets $A_i \subseteq \{1,2,\ldots,n\}$, with $1\leq i \leq N$, be such that for any $1\leq i < j \leq N$ we have $A_i \cap A_j$ being an interval. Prove that $\displaystyle N \leq \left \lfloor n^2/4 \right \rfloor$, and that this bound is sharp. (Dan Schwarz - after an idea by Ron Graham)
Problem
Source: Stars of Mathematics 2011 - Juniors - Problem 4
Tags: floor function, graph theory, combinatorics proposed, combinatorics