[BOJ] 회의실배정(1931)

[백준(BOJ)] 회의실배정(1931) C++

문제 : BOJ_1931번 회의실배정

문제 설명

그리디 알고리즘

유명한 그리디 문제입니다.

회의실이 하나 있고 N 개의 회의가 있는데,

회의마다 시작 시간과 끝나는 시간이 정해져있고

회의 시간은 겹칠 순 없지만 회의의 끝 시간과 다음 회의의 시작 시간이 겹칠 순 있습니다.

또 한, 시작 시간과 끝 시간이 동일한 경우도 있습니다.

이때 가능한 회의의 최대 개수를 구하는 문제입니다.

---

Solution

끝나는 시간이 빠른 회의를 선택하면, 뒤에 선택할 수 있는 회의의 수가 늘어나므로,

끝나는 시간대로 정렬하여 그리디하게 회의를 선택하는 것이 문제의 핵심입니다.

끝 시간 순으로 정렬을 하고, 이전 회의의 끝 시간보다 시작 시간이 늦는다면 최대 개수에 추가해 줍니다.


다만, 시작 시간과 끝나는 시간이 동일한 회의는 이전 회의가 어떻든 간에 영향이 없기 때문에, 무조건 추가해 줍니다.

---

Description

1. 시간 순으로 정렬을 하기 위해 우선순위큐를 썼습니다.
2. 자료형이 pair 일 때, 우선순위큐는 앞의 숫자가 기준이므로 {끝 시간, 시작 시간} 으로 push 했습니다.
3. 중간에 시작 시간과 끝 시간이 같으면 개수를 +1 해주고 다음 큐를 pop 했습니다.

---

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, result, beforeStartTime, beforeEndTime;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
// 오름차순인 우선순위큐가 필요하므로 greater<> 추가
int main(void) {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int startTime, endTime;
        cin >> startTime >> endTime;
        pq.push({ endTime,startTime });
        // pair의 첫 번째 인자가 기준 -> 끝 시간, 시작 시간 순으로 push
    }
    while (!pq.empty()) {
        int nowEndTime = pq.top().first;
        int nowStartTime = pq.top().second;
        pq.pop();
        if (beforeEndTime > nowStartTime) continue;
        // 앞 회의의 끝 시간이 지금 회의의 시작 시간보다 늦으면 넘어간다.
        if (nowEndTime == nowStartTime) {
            // 시작 시간과 끝 시간이 같으면 무조건 추가해준다.
            result++;
            beforeStartTime = nowStartTime;
            beforeEndTime = nowEndTime;
            continue;
        }
        result++;
        beforeStartTime = nowStartTime;
        beforeEndTime = nowEndTime;
    }
    cout << result << '\n';
}