Streaming Channels

Let the maximum streaming duration of one channel be $L$.

First, fix the ending time of the streaming interval as $t$. The earliest possible starting time is $\max(0,t-L)$, so for a fixed $t$ it is always optimal to use the interval $[\max(0,t-L),t]$. Session $i$ is contained in this interval if and only if

$$E_i \leq t \leq S_i+L.$$

Thus session $i$ adds $1$ to the range $[E_i,S_i+L]$ of possible ending times.

Conversely, if the starting time is fixed as $t$, the latest possible ending time is $t+L$. Session $i$ is contained if and only if

$$\max(0,E_i-L) \leq t \leq S_i.$$

Thus session $i$ adds $1$ to the range $[\max(0,E_i-L),S_i]$ of possible starting times.

Using sweep-line range-add events, for each $L$ we compute two functions.

• $P_L(T)$: the maximum number of sessions streamed by one interval whose ending time is at most $T$.
• $Q_L(T)$: the maximum number of sessions streamed by one interval whose starting time is at least $T$.

If channel A is operated before channel B, there is a boundary time $T$ such that the first interval ends at or before $T$ and the second interval starts at or after $T$. The best value for this order is

$$\max_T \left(P_{L_A}(T)+Q_{L_B}(T)\right).$$

The opposite order is handled similarly by computing $\max_T(P_{L_B}(T)+Q_{L_A}(T))$.

The values of these functions change only at event times. Therefore, it is enough to evaluate the formulas at the sorted union of their event times.

The time complexity is $O(N\log N)$ and the memory usage is $O(N)$.

Solution written by GPT5.5