⭐️ 난이도
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
N개의 강의에 대해서 각각의 시작 시간과 끝나는 시간이 주어졌을 때, 강의실을 얼마나 적게 사용할 수 있는지 구해야 하는 문제이다.
문제 지문에서 "Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다"고 주어져있다.
이 말은, i번째 강의의 시작시간 Si가 k번째 강의의 끝나는 시간 Tk보다 크거나 같다면, 해당 강의실에서 강의를 이어서 진행할 수 있다는 뜻이다.
강의실을 가장 적게 쓰려면 중간에 공백을 최대한 줄여야 한다.
그러기 위해서는 어떤 강의가 끝난 이후에 시간 시간이 제일 빠른 강의를 배치해야 한다.
priority_queue(우선순위 큐)를 이용해서 풀 수 있었는데, pq를 항상 올림차순으로 설정해놓고 강의의 끝나는 시간 만을 저장한다.
이후에 강의의 시작 시간과 pq의 값을 비교하여 만일 시작 시간이 더 빠르다면 pq에 push하여 강의실의 개수를 늘린다.
[전체적인 알고리즘]
1. 먼저 모든 강의를 시작 시간 - 끝나는 시간이 빠른 순서로 정렬한다.
2. 우선 첫 번째 강의의 끝나는 시간을 pq에 push한다.
3. 이제 두 번째 강의부터 마지막 강의까지 반복문을 통해 확인한다.
3-1. 만일 i번째 강의의 시작 시간이 pq.top()-[기존 강의의 끝나는 시간]과 같거나 더 크다면, 기존의 강의실을 계속 쓸 수 있다는 의미이다.
따라서 pq.pop() 이후 i번째 강의의 종료 시간을 pq에 push한다.
3-2. 만일 i번째 강의의 시작 시간이 pq.top()-[기존 강의의 끝나는 시간]보다 빠르다면, 기존의 강의실을 사용할 수 없고,
새로운 강의실에서 강의를 해야 한다.
따라서 i번째 강의의 종료 시간을 pq에 push한다.
4. 반복문을 모두 진행하고, pq의 size가 필요한 강의실의 개수이다.
⭐️ Code
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#define INF 987654321
#define MAX 1000000 + 1
using namespace std;
// 11000 - 강의실 배정
int n;
vector<pair<int, int>> lecture;
void input(){
cin >> n;
lecture.assign(n, {0,0});
for(int i = 0; i < n; i++){
cin >> lecture[i].first >> lecture[i].second;
}
sort(lecture.begin(), lecture.end());
}
int solve(){
priority_queue<int, vector<int>, greater<>> pq;
pq.push(lecture[0].second);
for(int i = 1; i < n; i++){
int startTime = lecture[i].first;
int endTime = lecture[i].second;
if(startTime >= pq.top()){ // 시작하는 시간이 끝나는 시간 이후라면
pq.pop();
pq.push(endTime);
}
else{
pq.push(endTime);
}
}
return pq.size();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
cout << solve();
return 0;
}
