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 < b_i \leq C$ . We say a pair of intervals $ I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $ > 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 < 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 < K < 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})$ .