https://www.acmicpc.net/problem/30827
문제요약
- 회의실을 사용할 수 있는 최대 개수 구하기
- 회의 수 : 20만, 회의실개수 : 3
접근법
- 회의 종료시간으로 정렬
- 빨리 끝나는 회의가 유리함
- 더 빨리 시작하는 회의를 선택하더라도, 회의실이 노는 시간은 줄겠지만, 회의가 안 끝나서 다른 회의가 들어올 기회가 없음
- 그리디 비슷하게 증명도 될 것 같음(빨리 끝나는 회의로 대체해도 동일하거나 유리한 효과가 있다!)
- 회의실을 선택할때 적절한 끝나는 시간을 갖는 것중 가장 느린 것을 선택하고 싶음
- 여러개가 있다면 빠른 것 보다는 늦게 끝나는 것을 선택하는게 유리함
- 이것도 그리디 비슷하게 증명 될 것 같음
- 적절하게 끝나는 것을 판단하고 + 가장 느린 것 선택은 정렬 + 이분탐색을 써야하지만...
- 다행히 회의실의 개수가 3개임 => 그때 그때 탐색해도 됨
newbieski