[BOJ/C++] 11000: 강의실 배정

🏅 GOLD 5

✏️ 1차 솔루션

• 강의 대기 큐: 우선순위 큐로 강의 시작시간, 종료시간 빠른 순으로 정렬
• 현재 강의중 큐: 우선순위 큐로 강의 종료시간 빠른 순으로 정렬

현재 시간을 늘려가면서 시작할 강의는 시작하고 끝낼 강의는 끝내기
1. 현재 강의중 큐에서 종료시간과 현재 시간 동일한 강의 있으면 pop 하기
2-1. 강의 대기 큐에서 시작시간과 현재 시간 동일한 강의 있으면 pop 하고 현재 강의중 큐에 push 하기
2-2. 현재 강의중인 큐가 강의실 개수보다 많거나 크면 강의실 추가하기

🚨 1차 trouble

시간초과 심각하고 답도 틀림

✏️ 최종 솔루션

1. 시작시간, 종료시간 빠른 순으로 우선순위 큐에 저장
2. 시작한 강의의 종료시간만 따로 종료시간 빠른 순으로 우선순위 큐에 저장
   3-1. 다음 강의 시작시간이 가장 빠른 종료시간보다 빠르면 우선순위 큐에 다음 강의를 저장
   3-2. 다음 강의 시작시간이 가장 빠른 종료시간보다 느리면 우선순위 큐에서 종료시간을 pop 하고 다음 강의를 저장
3. 모든 강의를 시작했을 때, 강의 중인 큐의 size 가 강의실의 개수

📌 self feedback

pair 큐를 2개로 돌리고 시간 count 를 따로 하면 반복문을 중첩으로 돌려야하기 때문에 비효율적

✏️ 최종 code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct cmp {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        if(a.first==b.first) return a.second>b.second;
        return a.first>b.first;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> wait;
    priority_queue<int,vector<int>,greater<>> fin;
    cin >> n;
    while(n--) {
        int s,t;
        
        cin >> s >> t;
        wait.push({s,t});
    }
    
    fin.push(wait.top().second);
    wait.pop();

    while (!wait.empty()) {
        // 강의실 추가
        if(wait.top().first>=fin.top()) fin.pop();

        fin.push(wait.top().second);
        wait.pop();
    }
    
    cout << fin.size() << endl;
}