[BOJ] 1931 회의실배정

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

 그리디 알고리즘의 대표주자 회의실배정이다.

 사실 다 아는 문제니까 그냥 넘어가도 되겠지 이러면서 이제까지 한번도 구현을 안해봤는데, 채점해보니까 처음에 틀렸다 ㅡㅡ

 풀이 방법은 가장 끝나는 시간이 빠른 회의, 만약 같다면 시작을 더 빨리 하는 회의부터 그리디하게 선택하는 것이다. 끝나는 시간이 빠른 건 끝나는 시간이 빠를수록 더 많이 회의를 진행할 수 있으니까 그렇다고 쳐도 대체 왜 시작을 더 빨리 하는 회의부터 선택하는지는 잘 몰랐었는데 틀리고 나서 생각해 보니까 (7,8), (8,8) 등의 회의가 존재하면 두개를 다 먹을 수 있더라.

 구현은 간단하게 STL sort를 이용해서 정렬했다. 아직도 sort를 사용자 정의 함수로 정렬하는 것에는 익숙하지 않다...

 난이도는 1.5/5 정도라고 생각한다.

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
bool compare(pair<int, int> a, pair<int, int> b)
{
    if(a.second<b.second) return true;
    else if(a.second>b.second) return false;
    if(a.first<b.first) return true;
    else return false;
}
 
int main()
{
    int n,time=0,s=0;
    vector<pair<int, int> > V;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        V.push_back(make_pair(t1,t2));
    }
    sort(V.begin(),V.end(),compare);
    for(int i=0;i<V.size();i++)
    {
        if(time<=V[i].first)
        {
            time=V[i].second;
            s++;
        }
    }
    printf("%d",s);
    return 0;
}