BOJ 28305 - 세미나 배정

July 2, 2023

가장 많은 날의 세미나 수를 이분탐색으로 찾아준다.

$i$ 세미나의 시작일로 가능한 범위는

$\text{Max}(1, a_i-T+1) \sim a_i$ 이다. 이를 $L_i, R_i$ 라 하자.

모든 세미나를 $L_i$ 기준으로 오름차순 정렬하고 시작하자.

$m$ 일만 겹치게 하는것이 가능하냐를 판별하고 싶을 때, deque 같은거에 아직 $m$ 개가 덜찼다면 항상 $L_i$ 에 세미나가 시작하게 해주고,

그렇지 않다면 $m$ 번째 이전의 세미나와 안겹치는 선에서 가장 왼쪽에 있는 값을 현재 세미나의 시작 일로 잡는다.

$m$ 번째 이전의 세미나가 $k$ 일에 시작한다면 $\text{Max}(k+T, L_i)$ 일에 시작해주면 된다.

You may also enjoy