[백준] 1100번: 강의실 배정 - C++

문제

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

11000번: 강의실 배정

---

설명

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, answer;

vector<pair<int, int>> classTime;
// 가장 작은 값이 우선순위가 되는 큐
priority_queue<int, vector<int>, greater<int>> mypq;

int greedy()
{
    mypq.push(classTime[0].second);
    
    for(int i = 1; i<classTime.size();i++)
    {
        if(mypq.top()>classTime[i].first)
            mypq.push(classTime[i].second);
        else
        {
            mypq.pop();
            mypq.push(classTime[i].second);
        }
    }
    return mypq.size();
}

int main()
{
    cin >> N;
    
    for(int i = 0; i< N; i++)
    {
        int S, T;
        cin >> S >> T;
        classTime.push_back(pair<int,int>(S,T));
    }
    
    sort(classTime.begin(), classTime.end());
    
    cout << greedy() <<endl;
    
}

 

 

 

우선순위 큐에는 끝나는 시간이 들어간다. mypq는 가장 작은 값이 우선순위가 되는 큐이다.

mypq의 top과 classTime[i]의 시작시간을 비교한다.

비교한 결과 mypq의 top이 classTime[i]의 시작시간보다 크다면, 새로운 강의실을 사용해야하므로

mypq에 classTime[i]의 끝나는 시간을 push해준다.

 

mypq의 top이 classTime[i]의 시작시간과 같거나 작다면, 해당 강의실을 사용할 수 있으므로

pop을 통해 top에 있는것을 제거해주고, classTime[i]의 끝나는 시간을 push해준다.

 

이 과정을 모두 반복한 후 mypq에 남아있는 element의 수가 사용해야하는 강의실의 수이다.