[우선순위 큐] 강의실 배정 - 백준 11000번

11000번: 강의실 배정

풀이

• Priority Queue의 장점인 넣을 때마다 정렬이 된 상태인 점을 활용한다.
• 최소 힙을 사용해서 빨리 끝나는 순으로 정렬하여 가장 빨리 끝나는 top의 끝나는 시간과 다음 강의 시작 시간을 비교한다.
  • top()에 있는 것보다도 작으면 새 강의실을 파야 한다.
  • top()에 있는 것보다 크거나 같으면 강의를 대체한다. (끝 시간 업데이트)
• 힙에 남아있는 queue의 사이즈가 결국 강의실의 개수이다.

실수

반례 (내림차순으로 입력을 받는 경우)

3
5 6
3 4
1 2

expected: 1
result: 3

입력을 받자마자 바로 넘기다보니 이 부분을 신경쓰지 못했다.

해결

입력을 vector<pair<int, int>> 로 받아 오름차순으로 sort 해주었다.

오름차순의 sort는 기본형인 sort(lectures.begin(), lectures.end());