BOJ 1931 : 회의실 배정

풀이요약

정렬

풀이상세

1. 끝나는 시간을 기준으로 정렬한다. 현재 시간이 끝나는 시간과 동일한 노드인 경우에만 카운팅을 추가한다.

2. {a,b} 가 존재할 때 모든 노드는 a 보다 b 가 클 수 밖에 없다. 더불어 동일한 b 의 노드에 대해서는 당연히 a 가 작은 것이 먼저 오는게 최적해에 도달할 가능성이 크다. (그래야 하나라도 더 카운팅 될 수 있으니). 따라서 b 를 기준으로 정렬을 한 후, 다음 b 보다 동일하거나 큰 a 를 찾는 경우가 가장 많은 회의실을 사용할 수 있는 경우이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;

bool cmp(pair<int,int> p1, pair<int,int> p2) {
    if(p1.second == p2.second) return p1.first < p2.first;
    return p1.second < p2.second;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
    cin >> N;
    vector<pair<int,int>> v(N);
    for(int i=0; i<N; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(),v.end(),cmp);
    int curr = v[0].second,cnt = 1;
    for(int i=1; i<N; i++) {
        if(curr <= v[i].first) {
            cnt++;
            curr = v[i].second;
        }
    }
    cout << cnt;
}