[BAEKJOON ONLINE JUDGE 1931번] 회의실배정

회의실배정 in C++

문제

• 여러 개의 회의가 하나의 회의실을 이용하고 싶어 한다. 이러한 상황에서, 회의실을 가장 효율적으로 이용하기 위해 회의실 사용표를 만들려고 한다.
• 각 회의의 시작 시간, 끝나는 시간이 주어질 때, 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하시오.

입력 데이터

• 각 회의는 시작 시간(0이상 2³¹-1이하인 정수)과 끝나는 시간(0이상 2³¹-1이하인 정수)을 가질 때, N개의 회의에 대해 N(1 ≤ N ≤ 10⁶), 각 회의의 시작 시간, 끝나는 시간
• 입력 예

20
39 45
24 25
25 27
34 37
35 50
36 40
6 40
30 37
34 38
24 39
15 32
44 45
49 50
1 29
40 41
22 23
1 22
20 41
40 47
24 39

출력 데이터

• 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수
• 출력 예

8

조건

• 단, 회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간과 끝나는 시간이 같을 수도 있는데, 이 경우에는 시작하자마자 끝나는 것으로 생각한다.

해결 방법

• 이 문제에 대하여 회의를 최대한 많이 선택하기 위해 회의를 선택하는 기준을 다음과 같이 생각해 볼 수 있다.
  • 진행 시간(= 끝나는 시간 – 시작 시간)이 가장 짧은 회의 부터 선택
  • 가장 적게 겹치는 회의 부터 선택
  • 가장 빨리 시작하는 회의 부터 선택
  • 가장 빨리 끝나는 회의 부터 선택
• 먼저 ‘진행 시간이 가장 짧은 회의 부터 선택하는 경우’에는 다음과 같은 반례가 존재한다.
  • 하루의 총 회의 가능 시간을 8시간이라 하자. 3개의 회의가 있고, 이 중 2개의 회의 진행 시간은 4시간(서로 겹치지 않음), 1개의 회의는 2시간 짜리 라고 한다.
  • 4시간 회의 2개를 하면 8시간으로 채워지지만, 2시간 짜리의 회의가 첫 번째 4시간 회의가 끝나기 1시간 전에 시작 되면, 이 회의를 선택 했을 때 다른 회의를 더 이상 선택할 수 없다.
• 다음으로 ‘가장 적게 겹치는 회의 부터 선택하는 경우’에는 다음과 같은 반례가 존재한다.
  • 하루의 총 회의 가능 시간을 15시간(0시14시)이라 하자. 회의1은 24시, 회의2는 68시, 회의3은 1012시, 회의4는 02시, 회의5는 46시, 회의6은 810시, 회의7은 1214시, 회의8은 24시, 회의9는 1012시, 회의10은 24시, 회의11은 1012시라 한다.
  • 이러한 경우에서 가장 많이 선택하려면 회의 4, 5, 6, 7을 선택해야 하지만 가장 적게 겹치는 회의는 회의2이다. 회의2를 선택하게 되면 최대 4개의 회의를 선택할 수 없게 된다.
• 세 번째 기준인 ‘가장 빨리 시작하는 회의 부터 선택하는 경우’에는 다음과 같은 반례가 존재한다.
  • 가장 빨리 시작하는 강의는 그 강의가 언제 끝날 지 모르므로 뒤의 강의를 배정할 수 없다.
  • 예를 들어서 가장 빨리 시작하는 강의가 하루 종일 강의를 한다면 그 경우는 최대 개수를 배정하지 못한 것이다.
• 그러나, ‘가장 빨리 끝나는 회의 부터 선택하는 방법’에는 반례가 존재하지 않는다. 이유는 다음과 같다.
  • 가장 빨리 끝나는 회의를 기준으로 회의 목록을 정렬 하고 가장 빨리 끝나는 회의를 선택한 뒤, 다음으로 빨리 끝나는 회의 들 중 이전에 선택된 회의가 끝나고 시작하는 회의를 선택하면 회의가 겹치지 않으면서 각 회의 사이의 공백을 최대한으로 줄일 수 있기 때문이다.
• 따라서 가장 마지막 기준인 ‘가장 빨리 끝나는 회의 부터 선택하는 방법’을 선택한다.

코드

#include <iostream>
#include <algorithm> // 벡터의 sort()를 하기 위해 include함
#include <vector>
using namespace std;

struct Meeting // 회의는 시작 시간과 끝나는 시간이 있음
{
    int startTime;
    int finishTime;
} typedef Meeting;

bool compare(const Meeting &m1, const Meeting &m2) // 회의를 정렬하는 기준
{ // 정렬 기준은 끝나는 시간을 기준으로 오름차순, 끝나는 시간이 같다면 시작 시간을 기준으로 오름차순
    if(m1.finishTime == m2.finishTime) return m1.startTime < m2.startTime;
    else return m1.finishTime < m2.finishTime;
}

int main()
{
    int n; // 회의의 개수
    cin >> n;

    Meeting m;
    vector<Meeting> M; // 회의 목록의 벡터
    vector<Meeting> ableMeeting; // 배정 가능한 회의 목록의 벡터

    for(int i = 0; i < n; i++) // 회의의 개수만큼 각 회의의 시작 시간과 끝나는 시간을 입력받아 벡터에 저장
    {
        cin >> m.startTime >> m.finishTime;
        M.push_back(m);
    }

    sort(M.begin(), M.end(), compare); // 위 compare함수를 이용하여 벡터M 정렬
    ableMeeting.push_back(M[0]); // 가장 먼저 끝나는 회의는 무조건 선택 가능함
    for(int i = 1, j = 0; i < n; i++)
    {
        if(ableMeeting[j].finishTime <= M[i].startTime) // 배정된 회의가 종료 후, 시작하는 회의는 배정 가능함
        {
            ableMeeting.push_back(M[i]);
            j++;
        }
    }

    cout << ableMeeting.size() << endl; // 배정 가능한 회의 목록의 벡터 크기 출력

    return 0;
}

문제 원본 링크

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