[백준] 11000 강의실 배정 c++

 

문제 링크 https://www.acmicpc.net/problem/11000

풀이 방법

먼저 시작하는 회의 순으로 정렬한다.

회의가 끝나는 시간을 저장하는 우선순위 큐(pq)를 하나 만든 후, 맨 앞의 회의가 끝나는 시간을 저장한다.

• 지금 회의가 pq의 top이후에 시작한다면(같은 회의실을 사용할 수 있다면) pq의 top을 꺼내고, 지금 회의의 끝나는 시간을 pq에 push한다.
• 그게 아니라면(다른 회의실을 사용해야 한다면) 회의가 끝나는 시간을 pq에 push한다.

모든 회의를 순회했을 때 결국 pq의 size가 회의실 갯수가 될것이다.

 

구현은 어렵지 않았으나 풀이 방법이 생각이 안나서 굉장히 까다로웠던 문제였다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int N;
int answer;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back({ start,end });
    }
    //먼저 시작하는 회의 순으로 정렬
    sort(v.begin(), v.end()); 
 
    pq.push(v[0].second);
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= pq.top()) {
            pq.pop();
            pq.push(v[i].second);
        }
        else {
            pq.push(v[i].second);
        }
    }
    cout << pq.size();
}