문제

https://www.acmicpc.net/problem/11666

해설

가능한 워크스테이션을 잠금 해제하지 않도록 최적의 스케줄링을 하는 문제입니다. m분이 지나면 자동으로 잠금이 되기 때문에, 이전 연구원이 떠나기 m분 전에 다음 연구원이 사용하도록 배정해주면 됩니다. 즉, 잠기지 않은 것 중 가장 먼저 연구원이 떠난 (잠기기까지 남은 시간이 가장 짧은) 워크스테이션에 배치하면 최적해를 구할 수 있습니다.

시간복잡도 계산

priority_queue를 사용하여 연구원이 떠난 시간을 $O(NlogN)$ 에 구할 수 있습니다. $1 \leq N \leq 300000$ 이므로, Greedy 알고리즘을 사용할 수 있습니다.

구현

먼저 연구원이 도착하여 사용하기 시작한 시간 $t_{arrive}$ 로 정렬합니다. priority_queue에 연구원이 떠난 시간 $t_{leave}$ 를 저장하고 다음 $t_{arrive}$ 과 비교하여

• $t_{leave} + m < t_{arrive}$ 이면 이미 잠긴 경우 -> priority_queue에서 제외
• $t_{leave} + m >= t_{arrive}$ 이면 아직 잠기지 않은 경우 -> 새로운 연구원 배치

로 해결할 수 있습니다.

소스 코드

http://boj.kr/d7d963b5c5064b758b3fe37e74bc67b3

---

참고