[백준 알고리즘] 1931번: 회의실배정

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

문제

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

풀이

그리디 알고리즘을 수업시간에 보고 적용해보기 위해 풀어 본 문제이다.

회의 시간을 최대한 촘촘히 배정하려면, 끝나는 시간이 제일 빠른 순서대로 사용시간을 따닥따닥 붙여주면 된다. 현재기준으로 끝나는 시간이 제일 빠른 구성을 선택하면 최대 갯수를 맞출 수 있을 것이다. 하나의 최선의 선택을 하고 나면 남은 시간들 속에서 또 최선의 구성을 선택해야되는 문제가 되니 문제의 크기가 계속 줄어들게 된다.

그리디 알고리즘은 주어진 배열을 미리 정렬해두고 순회하는 방법으로 문제를 해결하는데, 이번 문제에서 생각했어야하는 부분은 배열을 정렬할 때, 끝나는 시간이 여러개가 겹칠 경우 최적의 값을 얻지 못한다는 것이다.

끝나는 시간을 기준으로 정렬을 했을 때, 다음과 같이 정렬되었다고 하자, 이 구성에서 회의실을 배정해보면,

따라서 배정할 수 있는 회의실의 최대 갯수가 총 5개가 되는데, 사실은 그렇지 않다. 2번 인덱스와 3번인덱스를 교체해주면 배정할 수 있는 회의가 하나 늘어나기 때문이다.

위 구성으로 배열이 정렬된다면 6개의 회의실을 배정할 수 있게된다. 따라서 끝나는 시간을 기준으로 정렬할 때, 같은 값이 나오면 시작시간을 비교해서 더 빠른 시간을 앞에 두어야 한다.

이 문제를 풀 때는 pair, vector 를 이용해서 회의시간을 짝지어서 담고 정렬을 거친 뒤 for문으로 순회하는 방식을 사용했다.

std::sort가 기본적으로 지원하는 속도가 n log n 이기 때문에 최악의 경우에도 배열 전체를 순회하는 속도가 n 이기 때문에 O(nlogn)으로 해결할 수 있다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

bool pairSecondLess(const pair<int, int> &a, const pair<int, int> &b)
{
    if (a.second == b.second)
    {
        return a.first < b.first; // second 가 같으면 first가 작은 놈이 더 작다!
    }
    return (a.second < b.second);
}

int main()
{
    int N;
    scanf("%d", &N);
    vector<pair<int, int>> greedy;

    for (int i = 0; i < N; i++)
    {
        int s, f;
        scanf("%d %d", &s, &f);
        greedy.push_back(make_pair(s, f));
    }

    sort(greedy.begin(), greedy.end(), pairSecondLess); // 정렬할 때 인자로 위에서 정의한 함수를 준다.

    vector<pair<int, int>> v;
    v.push_back(greedy[0]); // 제일 처음은 끝나는 시간이 제일 빠른 구성이 들어간다.
    for (int i = 1; i < greedy.size(); i++)
    {
        if (v.back().second <= greedy[i].first) // 가장 마지막 최적의 구성과 비교
        {
            v.push_back(greedy[i]); // 현재 최선의 배정이 가진 끝나는 시간 이후에 시작할 수 있는 시간 중 끝나는 시간이 제일 빠른 구성을 넣어준다.
        }
    }

    printf("%ld", v.size());
}