[백준 알고리즘/C++/그리디] 11000 강의실 배정

 

 

[백준 알고리즘/C++] 1931 회의실 배정

회의실 배정과 비슷하지만 더 어려운 문제!

강의실 배정은 최소 몇 개의 강의실이 필요한지 출력해야 한다

 

 

한 강의가 끝나기 전에 시작하는 강의는 강의실을 따로 빌려야 하고,

강의가 끝난 뒤에 시작할 경우엔 그 강의실을 이어서 쓰면 된다

 

찾아보니 여러가지 코드가 많았지만 priority_queue를 사용하는게 난 가장 편하게 느껴졌다

따로 빌려야 할 경우엔 pq.push / 이어서 쓸 땐 그 강의를 교체한다는 느낌으로 pop, push를 해준다

마지막에 pq.size를 출력하면 강의실 개수가 된다

 

백문불여일견.. 백견불여일타..

 

비교하기 전에 시작시간 기준으로 sort 해줘야 함!

그래야지 지금 강의 끝나는 시간과 다음 강의 시작하는 시간을 유의미하게 비교할 수 있음

사실 회의실 배정 문제 때문에 끝나는 시간으로 정렬했다가 머리만 더 꼬였다

이건 희의 어쩌구 마냥 강의실 하나를 두고 최대한 많은 강의를 잡는게 아님

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, s, t;
    vector<pair<int, int>> v;
    priority_queue<int, vector<int>, greater<int>> pq;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        v.push_back(pair<int, int>(s, t));
    }
 
    sort(v.begin(), v.end());
    pq.push(v[0].second);
    
    int start, end;
    for (int i = 1; i < n; i++) {
        start = v[i].first;
        end = v[i].second;
 
        if (pq.top() > start)
            pq.push(end);
        else {
            pq.pop();
            pq.push(end);
        }
    }
 
    cout << pq.size();
}

 

맨 처음에 진짜 멍청이 같이 풀었음

회의실 배정과 같은 방법을 vector가 빌 때까지 반복하는 시간초과 급행열차 코드를 짬

 

 

 

+ 벡터보다 더 빠른게 있었다

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, s, t;
    priority_queue<int, vector<int>, greater<int>> pq;
 
    cin >> n;
    pair<int, int>* v = new pair<int, int>[n];
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
 
    sort(v, v + n);
    pq.push(v[0].second);
    
    int start, end;
    for (int i = 1; i < n; i++) {
        start = v[i].first;
        end = v[i].second;
 
        if (pq.top() > start)
            pq.push(end);
        else {
            pq.pop();
            pq.push(end);
        }
    }
 
    cout << pq.size();
}

 

pair<int, int>* v = new pair<int, int>[n];

이런식으로 쓸 생각은 못해봤다

아직 멀었다^^ㅎ

 

이정도 차이가 나니까 알아둬야 할 것 같음