[1931] 회의실배정

 

11

1 4 / 3 5 / 0 6 / 5 7 / 3 8 / 5 9 / 6 10 / 8 11 / 8 12 / 2 13 / 12 14

 

회의실을 사용할 수 있는 회의의 최대 수를 구하라.

위 예시의 답은

(1,4), (5,7), (8,11), (12,14) 입니다.

 

'그리디'하게 생각한 방법 중 하나는,

시작 가능한 회의 중에서 '종료시간'이 가장 빠른 것을 그 다음 회의로 배정하는 것입니다.

 

(1, 4)

(5, 7)

(8, 11)

(12, 14)

 

기준을 '회의시간'이 가장 짧은 것으로 잡으면 오답이 나옵니다.

(1, 4)

(5, 7)

(12, 14)

이렇게 끝나기 때문입니다.

 

1. 종료시간이 가장 빠른 것을 고릅니다.

2. 이전 회의의 종료시간보다 시작시간이 늦은 것들 중 종료시간이 가장 빠른 것을 고릅니다.

 

이를위해 종료시간이 빠른 순으로 앞에서부터 정렬해 놓고,

이전 회의의 종료시간을 보면서, 그보다 늦은 회의 중에서 첫번째 원소를 고릅니다.

 

소스코드

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;

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

int main() {
    int n, s, e;
    scanf("%d", &n);
    for (int i=0; i<n; i++){
        scanf("%d %d", &s, &e);
        v.emplace_back(make_pair(s, e));
    }
    sort(v.begin(), v.end(), compare_second);

    int end_time = v[0].second;
    int cnt = 1;

    for (auto it = ++v.begin(); it != v.end(); ++it){
        if (end_time <= it->first) {
            end_time = it->second;
            cnt++;
        }
    }
    printf("%d\n", cnt);
    

    return 0;
}