https://www.acmicpc.net/problem/11000
11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)
www.acmicpc.net
백준 1931(회의실 배정)문제와 비슷한 문제라고 생각해서 회의가 끝나는 시간을 기준으로 잡고 정렬(오름차순)을 해서 접근을 했다.
1차 시도. (결과: 시간초과)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<pair<int, int>, bool>> vec;
void input(){
cin >> N;
int start, finish;
for(int i = 0; i < N; i++){
cin >> start >> finish;
vec.push_back({{start, finish}, false});
}
}
bool compare(pair<pair<int, int>, bool> a, pair<pair<int, int>, bool> b){
if(a.first.second < b.first.second) return true;
else if(a.first.second == b.first.second){
if(a.first.first < b.first.first) return true;
return false;
}
return false;
}
int main(void){
cin.tie(NULL);
ios::sync_with_stdio(false);
input();
sort(vec.begin(), vec.end(), compare);
int result = 0;
while(N) {
int finish = 0;
result++;
for(int i = 0; i < vec.size(); i++){
if(!vec[i].second && vec[i].first.first >= finish){
vec[i].second = true;
finish = vec[i].first.second;
N--;
}
}
}
cout << result << endl;
return 0;
}배정이 된 시간표는 true로 표시하며 강의실 개수를 구하려고 했다.
그런데 이렇게 구현을 하게 되면 최악의 경우 200000 * 200000의 연산을 수행하기 때문에 시간 초과가 발생한다.
2차 시도 (결과: 시간 초과)
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N;
queue<pair<pair<int, int>, int>> q;
vector<pair<int, int>> vec;
void input(){
cin >> N;
int start, finish;
for(int i = 0; i < N; i++){
cin >> start >> finish;
vec.push_back({start, finish});
}
}
bool compare(pair<int, int> a, pair<int, int> b){
if(a.first < b.first) return true;
else if(a.first == b.first) {
if(a.second < b.second) return true;
return false;
}
return false;
}
int main(void){
cin.tie(NULL);
ios::sync_with_stdio(false);
input();
sort(vec.begin(), vec.end(), compare);
for(auto i: vec) q.push({i, 1}); //queue에 정렬된 데이터들을 복사
int result = 1;
int finish_time = 0;
while(!q.empty()) {
int start = q.front().first.first;
int finish = q.front().first.second;
int room = q.front().second; //몇번째 방인가
q.pop();
if(result < room) { //다음 방에 배치해야 됨
result = room;
finish_time = finish;
} else if(finish_time <= start) { //방에 들어올 수 있다면
finish_time = finish;
} else if(finish_time > start) {
q.push({{start, finish}, ++room});
}
}
cout << result << endl;
return 0;
}두 번째는 vector의 중복되는 true, false를 계산하지 않기 위해 queue를 이용해서 구하려고 했다.
그런데 이 또한
5
5 6
4 6
3 6
2 6
1 6와 같은 경우에서 O(N^2)의 연산이 나와 시간초과가 발생했다.
그래서 다른 블로그를 참고해서 문제를 해결하였다.
강의가 시작하는 시간을 기준으로 오름차순 정렬을 한 후 priority_queue를 이용해서 강의실 개수만 추가해주면 되는 문제였다.
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<int, int>> vec;
void input(){
cin >> N;
int start, finish;
for(int i = 0; i < N; i++) {
cin >> start >> finish;
vec.push_back({start, finish});
}
}
bool compare(pair<int, int> a, pair<int, int> b){ //강의 시작 시간을 기준으로 정렬
if(a.first < b.first) return true;
else if(a.first == b.first) {
if(a.second < b.second) return true;
return false;
}
return false;
}
int main(void){
cin.tie(NULL);
ios::sync_with_stdio(false);
input();
sort(vec.begin(), vec.end(), compare);
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(vec[0].second);
for(int i = 1; i < N; i++){
if(pq.top() <= vec[i].first)
pq.pop();
pq.push(vec[i].second);
}
cout << pq.size() << endl;
return 0;
}
참고 블로그
https://hyeonnii.tistory.com/181
[백준 11000] 강의실 배정
문제 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 정답 소스..
hyeonnii.tistory.com
