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

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

풀이

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

회의를 최대로 잡으려면 먼저 끝나는 회의부터 회의실을 사용할 수 있게 하면 된다.
회의가 빨리 끝나는 순서대로 정렬하고, 앞의 회의가 끝난 후 최대한 빨리 시작할 수 있는 회의를 다음으로 잡는다. (그리디 알고리즘)

코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    vector<pair<int, int>> v;
    for(int i=0; i<N; i++) {
        int s, e;
        cin >> s >> e;
        v.push_back({e, s});
    }
    
    sort(v.begin(), v.end());

    int end = v[0].first;
    int cnt = 1;
    for(int i=1; i<N; i++) {
        if(end > v[i].second) continue;
        end = v[i].first;
        cnt++;
    }

    cout << cnt;
    return 0;
}