백준 19598 최소 회의실 개수

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

 

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

#define INF 987654321

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue<int, vector<int>, greater<int>> res;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;


    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;

        pq.push(make_pair(s, e));
    }

    res.push(pq.top().second);
    pq.pop();

    while (!pq.empty()) {
        if (res.top() <= pq.top().first) {
            res.push(pq.top().second);
            res.pop();
        } else {
            res.push(pq.top().second);
        }
        pq.pop();
    }

    cout << res.size();

    return 0;
}

1. 문제

n개의 회의 시작 시각과 종료 시각이 주어진다. 이를 회의실에서 진행하려 하는데, 한 회의실에서는 동시에 한 회의만 가능하고, 각 회의는 도중에 중단될 수 없으며, 이전 회의의 종료와 동시에 다음 회의의 시작이 가능하다. 이 때, 필요한 회의실의 최소 개수를 구하라.

2. 풀이

 weight되지 않은 스케쥴링 문제이므로 그리디를 이용하여 풀 수 있다. 가장 먼저 시작하는 회의를 넣고 이와 비교하면서 우선순위 큐에 집어넣는다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue<int, vector<int>, greater<int>> res;

우선 입력받을 자료구조와 회의실을 나타내는 자료구조를 선언한다. 각 회의실에는 회의가 끝나는 시각이 들어간다.

 

for (int i = 0; i < n; i++) {
    int s, e;
    cin >> s >> e;

    pq.push(make_pair(s, e));
}

 각 회의의 시작시각과 종료시각을 입력받아 pq에 넣는다. 이 큐는 회의의 시작 순서대로 정렬되어 저장된다.

res.push(pq.top().second);
pq.pop();

 우선 첫 번째 회의를 시작한다. pq에 있는 회의 정보를 빼어 res에 집어넣는 식으로 구현한다.

while (!pq.empty()) {
    if (res.top() <= pq.top().first) {
        res.push(pq.top().second);
        res.pop();
    } else {
        res.push(pq.top().second);
    }
    pq.pop();
}

cout << res.size();

 새 회의가 들어올 때, 가장 일찍 끝나는 회의보다 늦게 시작한다면 종료된 회의를 res에서 빼고, 대신 다음 회의를 집어넣는다. 그런 회의가 없다면 새 회의실을 개설하여 회의를 넣는다. 연산이 끝나면 회의 리스트(pq)에서 해당 회의를 지운다.

 

 res는 회의실 리스트이므로 그 크기를 출력하면 정답을 구할 수 있다.