1931번 - 회의실 배정

해결방벙

그리디 방법으로 해결하였다.

증명

회의실을 가장 많이 사용 할 수 있는 경우는 1. 끝나는 시간이 빠른 것, 2. 시작시간이 빠른 것 순으로 정렬 하고 가능한 시간의 개수를 탐색하면 된다.
$$ END_{i} >= END_{j} \ (단, \ i는\ 가장\ 빨리\ 끝나는\ 회의, \ j는\ i제외한\ 회의, \ END는\ 이후\ 가능한\ 회의의\ 개수)$$
그러므로 끝나는 회의의 수가 가장 빠르면 더 많은 회의를 할 수 있다.

전체 소스

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
vector<pair<int, int>> time;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}
int main() {
    cin >> N;
    time.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> time[i].first >> time[i].second;
    sort(time.begin(), time.end(), cmp);
    int end = 0, ans = 0;
    for (int i = 0; i < N; ++i)
        if (end <= time[i].first) {
            ans++;
            end = time[i].second;
        }
    cout << ans << endl;
    return 0;
}