We are given $n$ intervals $[l_1,r_1], [l_2,r_2], [l_3, r_3], \dots,[l_n, r_n]$ in the number line. We can divide the intervals into two sets such that no two intervals in the same set have overlaps. Prove that there are at most $n-1$ pairs of overlapping intervals.
The given condition actually states that, no point in the number line is part of more than two intervals. Because, if some point was part of three or more intervals, we could not divide those intervals into two sets as they all overlapped each other.
We prove this by induction. Base case $n=2$ is trivial. Now, assume the statement is true for $n=k$. If there are $k+1$ intervals, consider the left-most interval, or to be exact, the interval with the least $r_i$. Notice that this interval can overlap at most one other interval otherwise it would not satisfy the given condition. Let's say we remove this interval, then we are back to $k$ intervals, which can have at most $k-1$ overlapping intervals. So for $k+1$ intervals, we can have at most $k-1+1=k$ intervals and we are done.
Remarks:
We are not actually done here. We must show at least one configuration with $n-1$ overlapping intervals. However, this configuration is easy enough. Just let every interval (except the left-most and right-most ones) overlap only its neighboring two intervals.
Gonitzoggoβ