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

문제 풀이

먼저 들어온 입력에 대해 시작시간으로 오름차순 정렬한다.
vector<pair<int,int>>를 쓰면 알아서 첫번째 요소 기준으로 된다 해서 그렇게 함

이렇게 하고나서 이제 pair를 순차적으로 살펴보는데
끝나는 시간을 우선순위 큐 minHeap으로 만들어놓고,

• 현재 시작하는 시간이 minHeap의 top보다 크거나 같으면 pop한다
• top보다 작으면 강의실 개수 +1
• 두 경우 모두 현재 끝나는 시간을 우선순위 큐에 넣어준다.

Code

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

struct minHeap{
    int time;
    minHeap(int t){
        time=t;
    }
    bool operator<(const minHeap &b)const{
        return time>b.time; // 내림차순 (최소힙)
    }
};

int main(){
    int N;
    int cnt=1; //처음엔 배정.

    vector<pair<int,int>> Class;

    cin>>N;
    for(int i=0;i<N;i++){
        int s,t;
        cin>>s>>t;
        Class.push_back(make_pair(s,t));
    }

    sort(Class.begin(), Class.end());

    priority_queue<minHeap> T; //최소 힙
    T.push(minHeap(0));

    for(int i=0;i<N;i++){
        int s=Class[i].first; //시작 시간
        int t=Class[i].second; //끝나는 시간

        if(T.top().time<=s){
            T.pop();
        }else{
            cnt++;
        }

        T.push(t);

    }
    cout<<cnt<<"\n";
}

🥲 실수

ㅋㅋㅋㅋㅋ 구조체 만들어놓고 prioty_queue로 씀.... 어이없ㄷㅏ~~!!