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

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

1931번: 회의실 배정

---

회의실 배정 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다.

만약 시작 시간이 가장 빠른 것을 선택하고, 이후 종료 시간보다 시작 시간이 크거나 같은 회의 중 시작 시간이 가장 작은 것을 선택한다면, 시작 시간이 가장 빨라도 회의 시간이 긴 경우 사용 가능한 회의의 수가 최대가 되지 않을 수 있습니다.

 

따라서 종료 시간이 가장 빠른 것을 선택하고, 종료 시간 이후 시작하는 것 중 가장 빨리 끝나는 것을 선택하면 됩니다.

즉, 종료 시간을 기준으로 정렬한 다음, 시작 시간이 전 회의가 종료 시간보다 같거나 크면 선택하면 됩니다. 

 

⚠️ 단,  종료 시간이 같은 경우 시작 시간이 오름차순이 되도록 정렬해야 합니다.

예를 들어 (1, 1), (3, 3), (2, 3)이 주어졌을 때, 시작 시간이 정렬되지 않으면 (1, 1), (3, 3)만 선택되고, (2, 3)은 선택되지 않을 수 있습니다. 

 

아래는 전체 코드입니다. 

#include <bits/stdc++.h>
using namespace std;

#define s first
#define e second

bool cmp(pair<int, int> a1, pair<int, int> a2){ 
    if(a1.e == a2.e) return a1.s < a2.s;
    return a1.e < a2.e;}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;

    vector<pair<int, int>> a;
    for(int i = 0; i < n; i++){
        int s, e; cin >> s >> e;
        a.push_back({s, e});
    }

    sort(a.begin(), a.end(), cmp);  // 시작/종료 시간이 오름차순이 되도록 정렬

    int cnt = 1;
    pair<int, int> cur = a[0];  // 먼저, 가장 빨리 끝나는 회의를 선택
    for(auto iter = a.begin() + 1; iter != a.end(); iter++){
        pair<int, int> nx = (*iter);    // 다음으로 가장 빨리 끝나는 회의
        // 다음 회의의 시작 시간이 이전 회의의 종료 시간보다 더 크거나 같은 경우 선택
        if(nx.s >= cur.e) {cnt++; cur = nx;}    
    }
    cout << cnt;
}