백준 1931번(회의실 배정) C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list;

    for (int i = 0; i < n; i++)
    {
        int start, end;
        cin >> end >> start;
        list.push_back(make_pair(start, end));
    }
    sort(list.begin(), list.end());

    int time = list[0].first;
    int ans = 1;
    int j = 0;
    for (int i = 1; i <= n; i++)
    {
        if (list[i].second >= time)
        {
            ans++;
            time = list[i].first;
        }
    }
    cout << ans;
}

회의실 배정의 기본 알고리즘은,

1. 끝나는 시간, end time 순으로 시간을 정렬한다.
2. 그 정렬한 배열에서, start time이 현재시간보다 같거나 클 경우, 그 회의를 수행한다.

이러한 간단한 그리디 알고리즘을 사용해주었다. 주의 할점은, pair을 이용한 vector에 입력을 받았는데, sort를 해주는 과정을 위해 end time을 먼저 입력으로 받아주었다.