백준 1931번 회의실 배정 with cpp

회의실 배정

문제링크 Q_1931

그리디 알고리즘 문제를 한 번 풀어보자.

회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는 문제이다.

• 회의가 겹치지 않으려면
  이전 회의의 끝나는 시간 <= 다음 회의 시작시간
• 회의의 최대 개수를 얻으려면
  일찍 끝나는 회의대로 정렬
  

이렇게 두 가지의 경우를 고려해야 한다.

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

bool compare(pair<int, int> a, pair<int, int> b)
{
    if(a.second < b.second) return true;
    else if(a.second > b.second) return false;
    if(a.first < b.first) return true;
    else return false;
}
int main()
{
    int N, time = 0, s = 0;
    vector<pair<int, int>> V;
    cin >> N;
    while(N--)
    {
        int t1, t2;
        cin >> t1 >> t2;
        V.push_back(make_pair(t1, t2));
    }
    sort(V.begin(), V.end(), compare);
    for(int i = 0; i < V.size(); i++)
    {
        if(time <= V[i].first)
        {
            time = V[i].second;
            s++;
        }
    }
    cout << s;
    return 0;
}

pair 의 first 는 시작시간 , second 는 끝나는 시간이기 때문에
compare 함수를 통해 second 기준으로 정렬해주고
회의를 하나 선택하면 s++ 해주고 time 변수에 해당 회의의 끝나는 시간을 저장한다.
그렇게 쭈욱 체크하면 된다!