백준 1931. 회의실 배정

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

1931번: 회의실 배정

 

이 문제는 주어진 예제의 입력에 답이있었다.

예제를 보면 종료시간의 오름차순으로 주어져있는데 아주 중요한 포인트다.

 

처음에 나는 시작하는 시간을 기준으로 정렬을 했다.

그런데 시작하는 시간을 기준으로 오름차순 정렬하게 되면 다음과 같이 입력이 주어지고

 

0 300

1 3

2 5

3 10

 

처음부터 탐색을 시작한다고 하면 첫요소가 끝나는 시간이 300이므로 1번의 회의밖에 못하게된다.

그러면 첫요소를 제외하고 두번째 요소부터 선택했을때, 세번째 요소부터 선택했을때.. 모든 경우에 대해 계산해줘야한다.

 

끝나는 시간을 기준으로 오름차순 정렬하게 되면 

1 3

2 5

3 10

0 300

한번의 루프만으로 답을 찾을수 있다.

 

또한 다음과 같이 입력이 주어지고 끝나는 시간 기준으로 오름차순하면

2 2

1 2

끝나는 시간이 동일하므로 첫번쨰 회의를 하고 끝나게 된다.

따라서 끝나는 시간 기준으로 오름차순하고 끝나는 시간이 같다면 시작하는 시간 기준 오름차순 정렬을 해줘야한다.

1 2 

2 2

 

그리디 알고리즘 문제는 그리디를 썼을때 답이 보장되는지 안되는지 확인하는 것이 중요한것 같다.

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

int n;
vector<pair<long long, long long>> v;

bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    if(a.second == b.second)
        return a.first < b.first;

    return a.second < b.second;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    // second 기준 오름차순 정렬하고 second 값이 같다면 first 기준 오름차순 정렬
    sort(v.begin(), v.end(), cmp);

    long long endTime = v[0].second;
    int cnt = 1;
    for(int i = 1; i < n; i++)
    {
        if(v[i].first < endTime) continue;
        cnt++;
        endTime = v[i].second;
    }

    cout << cnt;
}