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

그리디 알고리즘으로 문제를 해결할 수 있습니다.

회의가 빨리 끝날수록 다음 회의와 겹치지 않는데 유리합니다.

따라서 회의가 빨리 끝나는 순으로 정렬한 다음 겹치지 않게 적절히 회의를 선택하면 가장 많은 회의를 진행할 수 있습니다.

끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬합니다.

예를 들어, (2,2)와 (1,2)의 경우 (1,2) (2,2) 순으로 회의를 진행하면 2개의 회의를 모두 할 수 있지만 (2,2) 회의를 먼저 진행하면 (1,2) 회의를 진행할 수 없게 됩니다.

// boj s1 1931
// 회의실 배정

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b)
{
    if(a.first == b.first) return a.second < b.second;

    return a.first < b.first;
}

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

    int N;
    cin >> N;

    vector<pair<int, int>> v(N);
    for(int i=0; i<N; i++)
    {
        cin >> v[i].second;
        cin >> v[i].first;
    }

    sort(v.begin(), v.end(), compare);

    int endtime=0;
    int count=0;
    
    for(pair<int, int> i : v)
    {
        if(i.second>=endtime)
        {
            endtime=i.first;
            count++;
        }
    }

    cout << count;

    return 0;
}