Streaming Channels

채널의 최대 지속 시간이 $L$이라고 하자.

먼저 스트리밍 구간의 종료 시각을 $t$로 고정한다. 이때 가능한 가장 이른 시작 시각은 $\max(0,t-L)$이므로, 고정된 $t$에서 송출할 수 있는 세션의 수를 최대화하려면 구간 $[\max(0,t-L),t]$를 사용하면 된다. 세션 $i$가 이 구간에 포함될 필요충분조건은 다음과 같다.

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

따라서 세션 $i$는 종료 시각 $t$의 범위 $[E_i,S_i+L]$에 을 더한다.

반대로 스트리밍 구간의 시작 시각을 $t$로 고정하면 가능한 가장 늦은 종료 시각은 $t+L$이다. 세션 $i$가 포함될 필요충분조건은 다음과 같다.

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

따라서 세션 $i$는 시작 시각 $t$의 범위 $[\max(0,E_i-L),S_i]$에 을 더한다.

구간 덧셈 이벤트를 시각 순서대로 처리하면, 각 $L$에 대해 다음 두 함수를 만들 수 있다.

• $P_L(T)$: 종료 시각이 $T$ 이하인 하나의 스트리밍 구간으로 송출할 수 있는 세션 수의 최댓값.
• $Q_L(T)$: 시작 시각이 이상인 하나의 스트리밍 구간으로 송출할 수 있는 세션 수의 최댓값.

채널 A가 먼저 운영되고 채널 B가 나중에 운영되는 경우에는 어떤 경계 시각 $T$가 존재하여 앞 채널은 $T$ 이하에서 끝나고 뒤 채널은 $T$ 이상에서 시작한다. 이 경우의 최댓값은 다음과 같다.

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

채널 B가 먼저 운영되는 경우도 같은 방식으로 $\max_T(P_{L_B}(T)+Q_{L_A}(T))$를 계산한다.

각 함수의 값은 구간 덧셈 이벤트가 발생하는 시각에서만 바뀐다. 그러므로 두 함수의 이벤트 시각을 모아 정렬한 뒤, 그 시각들에 대해서만 위 식을 평가하면 충분하다.

이 알고리즘의 시간 복잡도는 정렬 때문에 $O(N\log N)$이고, 메모리 사용량은 $O(N)$이다.

Solution written by GPT5.5