[BOJ] 1931. 회의실배정

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

1931번: 회의실배정

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 회의 수를 찾으면 된다.

 

 

문제에서 주어진 예제만 봐도 회의 진행시간이 짧은 순서로 진행하면 안 된다는 것을 알 수 있다. 물론 시작하는 시간이 빠른 것도 안된다. 한참 헤매다가 끝나는 시간을 기준으로 하면 된다는 것을 깨달았다...

 

 

끝나는 시간을 오름차순으로 정렬하여서 먼저 끝나는 회의를 진행하고 그 회의 바로 다음에 할 수 있는 끝나는 시간이 가장 빠른 회의를 진행하면 된다.

 

 

나는 벡터에 시작시간과 끝나는 시간을 pair로 넣어서 정렬했다.

pair는 first값을 기준으로 먼저 정렬되고 그다음으로 second값을 기준으로 정렬되기 때문에 

끝나는 시간을 앞에 넣어주었다. 그러면 끝나는 시간이 빠른 순으로 정렬된다.

#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    int s, e;
    vector<pair<int, int> > vt;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> s >> e;
        vt.push_back(make_pair(e, s));
    }
 
 
    sort(vt.begin(), vt.end());
 
 
    //끝나는 시간
    int now = vt[0].first;
    
    //회의 수
    int ans = 1;
 
    for (int i = 1; i < n; i++) {
        //현재 회의가 끝나는 시간 보다 빨리 시작하는 회의는 진행하지 못한다.
        if (vt[i].second < now) continue;
 
        //다음 회의가 끝나는 시간
        now = vt[i].first;
        ans++;
    }
 
    cout << ans << '\n';
 
    return 0;
}