[백준] 1931: 회의실 배정

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

1931번: 회의실 배정

정말 전형적인 Greedy Algorithm 문제이다.

그러면 어떤 내용을 기준으로 잡아야하는지 고민해보아야 한다.

 

회의가 시작한 순으로 정렬을 하면 최대 회의의 수를 구할 수 없다.

왜냐하면 회의는 일찍 시작했으나 늦게 끝나는 경우가 있기 때문이다.

따라서 회의가 끝나는 순대로 오름차순 정렬을 하고, 최대한 앞에서부터 채운다는 느낌으로 회의의 수를 세면 된다.

 

정렬 기준으로 회의의 종료 시간을 설정하기 위해서 회의에 대한 정보를 저장할 때 vector에 first에 종료 시간을, second에 시작 시간을 설정한다. 이렇게 하면 별도의 비교함수를 설정하지 않아도 된다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector<pair<int,int>> meetings;

int main(void) {
    int t, a, b;
    int max_num = 0, end = 0;
    cin >> t;
    while(t--) {
        cin >> a >> b;
        meetings.push_back(make_pair(b,a));
    }
    sort(meetings.begin(), meetings.end());

    for(auto m : meetings) {
        if(end <= m.second) {
            end = m.first;
            max_num++;
        }
    }
    cout << max_num << endl;
}