BOJ 1374 강의실

N개의 강의와 각 강의의 시작 시간과 종료 시간이 주어진다. 이 때, N개의 강의를 진행하는 데 필요한 최소의 강의실 개수를 구하는 문제이다.

고민하다가 질문 게시판을 봤는데, 시작 시간과 종료 시간을 따로 정렬해놓고 각 수업이 아닌 시간의 흐름에 따라서 생각해보라는 답변이 있어서 일단 각 강의의 시작 시간과 종료 시간을 따로 정렬해놓고 생각해봤다.

8
6 15 21
7 20 25
1 3 8
3 2 14
8 6 27
2 7 13
4 12 18
5 6 20 

문제의 입력 예제를 가지고 시작 시간과 종료 시간을 따로 정렬해보면

시작 시간 : 2  3  6  6  7 12 15 20

종료 시간 : 8 13 14 18 20 21 25 27 

뭔가 해보고 싶은 느낌이 든다. 바로 종료시간과 시작시간을 연결하는 것이다. 

종료시간 8이상의 가장 작은 시작시간은 12이다. 그리고 13 -> 15, 14->20 이렇게

연결 하면 연결되지 않은 2 3 6 6 7 이렇게 5개의 시작시간이 남는데 바로 5개가 

필요한 강의실의 최소 개수이다.

사실 처음에는 저렇게 그려놓고 연결해보니 느낌으로는 연결되지 않은 것의 개수가 

답이라는 것을 알겠는데, 왜 답인지는 바로 생각이 나지 않았다. 고민하다가 (사실

여전히 좀 헷갈리지만) 깨달음을 얻었는데, 자 설명을 해보겠다.

일단 종료시간과 시작시간을 연결할 때는 종료시간 이상의 가장 작은 시작시간과 

연결해야 한다. 그래야 최대한 많은 연결을 할 수 있기 때문이다. 그렇다면 연결하는 

것은 무슨 의미일까? 종료시간과 시작시간을 연결할 수 있다는 것은 강의실을 바꾸지 

않고 이어서 쓸 수 있다는 의미이다. 여기까지는 쉽다. 

이제 종료시간과 연결된 시작시간을 보자. 종료시간과 연결된 시작시간은 방금 말했듯이

원래 누가 쓰던 강의실에서 시작하는 것을 의미한다. 그렇다면 종료시간과 연결되지 못한

시작시간은 무엇을 의미할까? 이것이 중요하다. 종료시간과 연결되지 못한 시작시간은

누군가 쓰던 강의실을 이어서 쓰기에는 시간이 안 맞기 때문에(혹은 첫 강의라서) 새로운

강의실을 써야한다는 것을 의미한다.

즉 연결되지 않은 시작시간의 최소 개수는 새로운 강의실을 써야하는 최소 경우이고, 

N개의 강의를 진행하는데 필요한 강의실 개수의 최소값이 된다.

그 답변의 도움이 있어서 여기까지 생각할 수 있었다... 풀어봐야겠다.

AC를 받았다.