[백준 / C++] 11000번 강의실 배정

문제 재정의 및 추상화

결론: 강의의 시작 시간과 끝나는 시간을 고려해 최대한 적은 강의실을 사용하도록 스케줄링하라.

문제 접근 방식

끝나는 시간을 우선으로 생각하여 접근해야 한다.
-> 우선순위 큐를 써보자!

해법을 찾는데 결정적이었던 깨달음

📌 우선순위 큐에 남아있는 시간의 개수가 최종적으로 필요한 강의실의 수다.

문제 풀이 로직

1. 수업의 개수 n을 입력받는다.
2. n번 반복하며 pair vector st에 시작 시간과 끝나는 시간을 입력받는다.
3. st를 시작 시간 기준, 시작 시간이 같으면 끝나는 시간을 기준으로 정렬한다.
4. st 사이즈만큼 반복하며 아래를 수행한다.
   4-1. 정렬된 끝나는 시간을 우선순위 큐 t에 담는다.
   4-2. 만약 st의 시작 시간보다 작은 값이 top이라면 pop 한다.
5. t의 사이즈를 출력한다.
   
   

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, tmp1, tmp2;
    vector<pair<int, int>> st;
    priority_queue<int, vector<int>, greater<int>> t;
    
    cin >> n;
    
    while(n--){
        cin >> tmp1 >> tmp2;
        st.push_back(make_pair(tmp1, tmp2));
    }
    
    sort(st.begin(), st.end());
    
    for(int i = 0; i < st.size(); i++){
        t.push(st[i].second);
        if(t.top() <= st[i].first) t.pop();
    }
    
    cout << t.size();
    
    
    return 0;
}