⭐️ 난이도
Gold 5
⭐️ 문제
https://www.acmicpc.net/problem/11000
11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
www.acmicpc.net
⭐️ Idea flow
그리디(Greedy) 알고리즘을 사용해서 풀어야하는 문제였다.
전체적인 알고리즘은 다음과 같다.
1. 시작하는 시간을 기준으로 강의 정보(lecture)를 정렬한다.
2. 처음 시작하는 강의(lecture[0])의 끝나는 시간을 우선순위 큐에 push한다.
여기서 우선순위 큐는 작은 수의 우선순위를 더 높게 잡는다.
3. 인덱스 1부터 시작하는 반복문을 실행한다.
3-1. i번째 강의의 시작하는 시간이 i-1번째 강의의 끝나는 시간과 같거나 느리다면, 해당 강의실에서 강의를 이어할 수 있다. 따라서 우선순위 큐에서 원소 하나를 pop한 후, 현재 강의의 끝나는 시간을 우선순위 큐에 push한다.
3-2. i번째 강의의 시작하는 시간이 i-1번째 강의의 끝나는 시간보다 빠르다면, 해당 강의실에서 강의를 이어할 수 없다.
따라서 우선순위 큐에 현재 강의의 끝나는 시간을 우선순위 큐에 push한다.
4. 반복문을 모두 완료 했을 때, 우선순위 큐에 들어있는 원소의 개수가 바로 필요한 강의실의 개수이다.
그렇다면 의문이 생긴다.
혹시나 서로 다른 강의가 하나의 강의를 동시에 선택할 가능성은 없는가?
결론부터 말하면 없다.
반복문으로 선형적으로 진행한다는 이유도 있고, 만일 다른 두 강의가 같은 시간에 끝났다고 하더라도
둘 중 하나의 강의가 먼저 선택을 진행하기 때문에 동시에 선택할 가능성은 없다고 봐도 무방하다.
⭐️ Code
