[BOJ/C++] 1931 - 회의실 배정

문제

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

1931번: 회의실 배정

풀이

끝나는 시간이 빠른 순서대로 회의 시간을 정렬한 후 가능한 회의를 순서대로 선택을 하면 되는 그리디 문제이다.

그리디는 귀류법으로 가설을 증명하는데 실제 코딩테스트 환경에서는 그렇게 풀 수 없고 눈에 보이는 문제면 바로 풀어보고 긴가 민가하면 마지막에 푸는게 낫다고 한다.

코드

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

#define pii pair<int, int>

vector<pii> v;
int n;

bool cmp(pii a, pii b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}

int ans = 0;

void solve(int prev, int cnt) {
    for (int i = prev + 1; i < n; i++) {
        if (v[prev].second <= v[i].first) {
            solve(i, cnt + 1);
            break;
        }
    }
    ans = max(ans, cnt);
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        pii t;
        cin >> t.first >> t.second;
        v.push_back(t);
    }
    sort(v.begin(), v.end(), cmp);
    solve(0, 1);
    cout << ans;
    return 0;
}