1931번: 회의실배정

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


$O(nlgn)$

끝나는 시간을 기준으로 정렬한다.(같다면 시작하는 시간을 기준으로 오름차순, 이는 시작하자마자 끝나는 회의를 고려하기 위함이다.)
정렬한 순서대로 보면서 기존의 스케줄에 추가할 수 있으면 추가한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, r, e;
pair<int, int> p[MXN + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].second, &p[i].first);
    sort(p, p + n);
    for (int i = 0; i < n; i++) if (p[i].second >= e) e = p[i].first, r++;
    printf("%d", r);
    return 0;
}