[백준] 11000 강의실 배정

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

11000번: 강의실 배정

---

각 수업의 시간이 겹칠 경우 강의실이 추가된다. 단, 한 수업의 끝 시간과 시작 시간이 동일하면 겹치지 않는 것으로 한다. 

 

먼저 수업들을 시작 시간을 기준으로 정렬한다. 그리고 이미 시작한 수업을 끝나는 시간을 기준으로 우선순위 큐에 삽입한다. 이미 시작한 수업의 끝 시간과 다음에 시작할 수업의 시작 시간을 비교하며 수업이 겹치지 않는 경우, 우선순위 큐에서 수업을 제거한다.

 

최종적으로 우선순위 큐에는 수업 시간이 겹치는 수업들만 남아있게된다.

 

수업이 끝나는 시간을 기준으로 정렬하지 않는 것에 대해 의문을 가질 수 있다. 만약 끝 시간을 기준으로 정렬하면, 늦게 시작 했지만 먼저 끝나는 수업이 있는 경우가 있을 수 있다. 이로 인해 일찍 시작하는 수업이 지연된다. 따라서 끝 시간을 기준으로 정렬하게 되면 위 문제는 해결할 수 없다.

 

Python

Java