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

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

int n;

bool compare(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second != b.second) {
        return a.second < b.second;  // 기본적으로 종료 시간을 기준을 오름차순 정렬
    }
    return a.first < b.first;  // 종료 시간이 같은 경우에는 시작 시간이 빠른것을 기준으로 오름차순 정렬
}

void solve() {
    // 그리디 설정 기준
    // 회의 시작 시간이 빠른 것을 기준으로 선택하는 경우, 시작이 빠르더라도 회의 시간이 오래 걸리면 많은 회의 진행 불가
    // 회의 시간이 짧은 것을 기준으로 선택하는 경우, 두 회의에 걸치는 경우 연속 배정에 방해 됨. 즉, 빈 시간이 많아지게 됨
    // 회의 종료 시간이 빠른 것을 기준으로 선택하는 경우, 회의가 빨리 끝날수록 더 많은 회의를 배정할수 있으므로 이를 선택
    cin >> n;
    vector<pair<int, int>> meetings;
    for (int i = 0; i < n; ++i) {
        int s, e;
        cin >> s >> e;
        meetings.push_back({s, e});
    }
    sort(meetings.begin(), meetings.end(), compare);  // 종료 시간을 기준으로 오름차순 정렬
    pair<int, int> selected = { meetings[0].first, meetings[0].second };
    int cnt = 1;  // 첫 회의 배정
    for (size_t i = 1; i < meetings.size(); ++i) {
        if (selected.second <= meetings[i].first) {  // 선택한 회의의 시작 시간이 앞 회의의 종료시간보다 빠르지 않은 경우 선택
            selected = meetings[i];
            cnt++;
        }
    }
    cout << cnt << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}