백준 11000 (강의실 배정)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

백준 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] 강의실 배정