BOJ 1931 회의실 배정

boj 1931 회의실 배정

그리디 알고리즘 문제의 풀이 흐름에 따라 풀었다.

1. 현재 시간을 t라고 할 때, t이상의 회의들 중에 가장 먼저 끝나는 회의를 선택하는 것이 최선이라고 생각했다.
2. 증명까지는 하지 못했고, 그림을 그려보고 당장 손해이지만 나중에는 이득인 경우가 있나 확인해보았다.
3. 입력 받은 회의의 시간들을 끝나는 시간이 빠른 순으로, 끝나는 시간이 같을 때는 시작하는 시간이 빠른 순으로 정렬한 후에 가장 먼저 끝나는 회의를 찾는 방식으로 구현했다.

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

int N;
int ans = 0;
int t = 0;
pair <int, int> p[100005];

bool compare(const pair<int, int>& p1, const pair<int, int>& p2)
{
    if (p1.second < p2.second) return true;
    else if (p1.second == p2.second) return p1.first <= p2.first;
    else return false;
}

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
    sort(p, p + N, compare);

    for (int i = 0; i < N; i++)
    {
        if (t > p[i].first) continue;
        ans++;
        t = p[i].second;
    }

    cout << ans;

    return 0;
}