BOJ 백준 1931 : 회의실 배정

시작하면서

　이번 문제는 그리디 알고리즘 중 활동 선택 문제(Activity Selection Problem) 문제이다.

BOJ 1931 - 회의실 배정

​

문제 이해

​ 이 문제는 활동 선택 문제의 기본적인 문제이다. 방법은 다음과 같다.

1. 가장 일찍 끝나는 회의를 찾는다.
2. [1.]에서 찾은 회의의 시작 시간이 현재 끝난 회의 시간과 같거나 크면 회의실에서 사용이 가능하므로 사용한다.

​ 1번과 2번을 재귀적으로 반복하면 문제가 해결된다. 물론 반복문으로도 가능하다(활동 선택 문제로 구글링하면 많이 나오니 패스).

​ 이를 좀 더 효율적으로 하기 위해서 처음에 퀵정렬을 사용해서 1:끝나는 시간과 2:시작 시간을 기준으로 정렬하고 문제를 해결한다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int _compare(const pair<int, int> a, const pair<int, int> b)
{
    // 1. 끝나는 시간을 기준으로 오름차순
    if (a.second < b.second)
    {
        return 1;
    }
    // 2. 끝나는 시간이 같을시
    else if (a.second == b.second)
    {
        // 2-1. 시작 시간을 기준으로 오름차순
        if (a.first < b.first)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}

int ActivitySelectionProblem(const vector<pair<int, int> >& v, int currentIndex)
{
    int currentEndTime = v[currentIndex].second;

    for (int i = currentIndex + 1; i < v.size(); i++)
    {
        if (v[i].first >= currentEndTime)
        {
            return ActivitySelectionProblem(v, i) + 1;
        }
    }

    return 1;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<pair<int, int> > v;
    int N;

    cin >> N;

    v.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), _compare);

    cout << ActivitySelectionProblem(v, 0);

    return 0;
}