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

※ 문제

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

1931번: 회의실 배정

 

※ 풀이

1) 너무너무 유명한 `그리디 알고리즘` 문제입니다.
2) 회의 시간이 `일찍 끝나는 순`으로 오름차순 정렬합니다.
3) 현재 회의 시간이 끝나는 시간보다 후에 시작하는 회의가 존재할 때마다 횟수를 카운트하고, 다음 회의가 끝나는 시간을 저장하여 반복합니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, a, b, ans;
vector<pair<int, int>> arr;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        arr.push_back({ b,a });
    }
    sort(arr.begin(), arr.end());

    a = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i].second >= a)
        {
            a = arr[i].first;
            ans++;
        }
    }
    cout << ans;
}