Upper bound on the average number of overlaps for an interval within a set of intervals Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded by a constant $C$ i.e. $0 \leq a_i &lt; b_i \leq C$. We say a pair of intervals $I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $&gt; 0$. 

Define a function $F(i)$ which computes the number of intervals in $\mathcal{I} \backslash I_i$ that interval $I_i$ overlaps with.
\begin{equation}
F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j)
\end{equation}
where the function $Overlap(I_i, I_j)$ is an indicator function which returns 1 if $I_i, I_j$ overlap, else it returns 0.

The average number of overlaps for the intervals in $\mathcal{I}$, denoted by $Avg(\mathcal{I})$ is given by $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

The question is, suppose we are allowed to choose the intervals in the set $\mathcal{I}$ with the following additional conditions:


For any $t \in [0, C]$, we have at most $M$ (and $M &lt; L$) intervals in $\mathcal{I}$ such that $t$ is contained within those $M$ intervals. Stated differently, at most $M$ intervals overlap at any point in time. 
Any interval in $\mathcal{I}$ overlaps with at most $K$ other intervals, and $M &lt; K &lt; L$.


then, what is an upper bound on $Avg(\mathcal{I})$ for any choice of the intervals in $\mathcal{I}$ satisfying 1, 2?

In case you are wondering, this problem is of interest to me in order to be able to study the run-time of a scheduling algorithm. 

I am unable to come up with a non-trivial upper bound for $Avg(\mathcal{I})$ and would be interested to know if the problem I stated has been studied. I am also open to ideas on how one may be able to obtain a tight upper bound for $Avg(\mathcal{I})$.
If we ignore $L$ and focus only on the parameters $C,K,M$, the following upper bound is asymptotically tight, i.e., it's about the best you can do, up to a constant factor:

$$\text{Avg}(\mathcal{I}) \le \min(MC,K).$$



Proof that it's an upper bound: Fix any interval.  We're promised that it overlaps with at most $K$ others.  Also, the interval has at most $C$ points in it, so by a union bound over those points, we can also infer it overlaps with at most $MC$ others.  Therefore, it overlaps with at most $\min(MC,K)$ others.  Now the average of a bunch of numbers that are all $\le \min(MC,K)$ will itself be $\le \min(MC,K)$.



Proof that it's tight: I will show the construction of a set of intervals where $\text{Avg}(\mathcal{I}) \sim \min(MC,K)/4$.  There are two cases:


Case 1: $K \ge MC$.  Then use $M/2$ copies of each interval of the form $[i,i]$ (i.e., each length-0 interval), and use $M/2$ copies of the interval $[1,C]$.  You can observe that the latter each intersect with $\sim MC/2$ other intervals (and all intersect with fewer than $K$).  So, the average is about $MC/4$.  This gives a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.
Case 2: $K &lt; MC$.  Set $C' = K/M$, apply the above construction to the interval $[1,C']$ instead of $[1,C]$, and we obtain a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.




If you also care about the dependence on $L$,  you might be able to build on the above analysis to see how it might depend on $L$.