오늘 풀어본 문제는 BOJ 11000 강의실 배정 이다. 정말 오랜만에 그리디 알고리즘을 골라 풀어봤더니 좀 심각한것 같다 ㅎ 몇개 더 풀어봐야겠다,,
BOJ 11000 강의실 배정
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
입출력
[입력]
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
[출력]
강의실의 개수를 출력하라
풀이
이렇게 저렇게 풀이 방법을 생각해봤지만 그리디 알고리즘을 적용하지 못했다. 문제의 알고리즘 분류를 보니 정렬, 우선순위 큐를 사용한다고 되어 있길래 거기서 조금 감을 잡았지만 결과적으로는 포스팅을 참고해 해결해야 했다..! 아쉽다!
그리디 알고리즘이라는 것은 결국 우선순위가 결정되는 기준에 따라 알고리즘이 진행된다는 것인데, 그럼 그 기준이 무엇인지를 생각하는 것이 가장 포인트인 것 같다.
여기서의 기준은 강의가 끝나는 시간 T이다!
강의들을 시작 시간을 기준으로 정렬하고 첫번째 강의부터 그 종료 시간을 우선순위 큐에 넣어준다. 우선순위 큐는 기본적으로 maxHeap 이기 때문에 priority_queue<int, vector<int>, greater<int>> 와 같이 선언하던가 혹은 마이너스를 붙여 minHeap으로 활용한다.
강의 시작 시간 순서대로 강의들을 탐색하면서 해당 강의가 현재 가장 빠르게 끝나는 강의보다 먼저 시작한다면 새로운 강의실이 필요하다는 뜻이다. 우선순위 큐에 새로운 강의를 넣어준다.
반대로 강의가 현재 가장 빠르게 끝나는 강의보다 늦게 시작한다면 새로운 강의실은 필요하지 않고 해당 강의실이 비는 시간이 새로운 강의의 종료 시간이 되는 것 이므로 우선순위큐를 하나 pop 하고 새로운 강의의 종료 시간을 push한다.
탐색이 끝나면 우선순위 큐에 남아있는 원소의 수가 필요한 최소의 강의실 개수를 의미한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
// boj 11000 강의실 배정, 골드 5, 그리디
using namespace std;
bool byStart(pair<int, int> a, pair<int, int> b){ // 강의 시작 시간 기준 오름 차순 정렬
return a.first<b.first;
}
int getMinRoom(int N, vector<pair<int, int>> lecture){
sort(lecture.begin(), lecture.end(), byStart);
priority_queue<int, vector<int>, greater<int>> pq; //종료시간이 빠른 순서대로
pq.push(lecture[0].second);
for (int i = 1; i < N; ++i) {
if (pq.top()<=lecture[i].first) pq.pop(); // 현재 가장 빨리 끝나는 강의실을 이용할 수 있다면
pq.push(lecture[i].second);
}
return pq.size();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin>>N;
vector<pair<int, int>> lecture(N, {-1,-1});
for (int i = 0; i < N; ++i) {
cin>>lecture[i].first>>lecture[i].second;
}
cout<<getMinRoom(N, lecture);
return 0;
}