JUNGOL 알고리즘 1370 : 회의실 배정

회의실이 하나 있다. 여러 회의들이 시작시간과 종료시간이 예약되어 있으며, 시간대가 겹치는 회의는 동시에 개최가 불가능하다. 따라서 같은 시간대에 속하는 회의들 중 하나만 개최하고 나머지 회의들은 버려야한다. 

단, 종료시간과 시작시간이 같은 경우에는 시간이 겹친다고 말하지 않는다. 회의의 개수 N과 각 회의의 시작시간, 종료시간이 주어졌을 때 되도록 많은 회의를 개최하고자 한다.

 

회의를 최대한 많이 배정하는 프로그램을 작성하시오.

 

첫줄에는 회의의 수 N(5≤N≤500), 둘째 줄부터 i-1번 회의의 번호와 시작시간과 종료시간이 차례로 주어진다.
(500 이하의 자연수)

첫줄에는 배정 가능한 최대의 회의수를 출력하고 다음 줄부터는 배정한 회의의 번호를 시간대순으로 출력한다.
만약, 답이 여러 가지(최대회의수가 될 수 있는 배정 방법이 여러가지)라면 그 중 아무거나 하나 출력한다.

6 1 1 10 2 5 6 3 13 15 4 14 17 5 8 14 6 3 12

3 2 5 4

---

시간이 겹치지 않도록 회의실을 배정하고 그 배정하는 숫자가 가장 크게 되는 배정 방법을 찾는 문제인 것으로 보입니다.

문제 힌트에서는 그리디를 사용하라고 되어있는데, 그리디는 개념상 현재 선택할 수 있는 것 중 가장 최적인 것을 선택하여 진행하는 방법으로 알고 있습니다.

그러므로 시작위치를 입력의 처음부터 끝까지로 바꾸면서 각 시작 위치에서 다음에 예약할 수 있는 시간이 이전 회의가 끝나는 시간과 가장 가까운 것을 선택하도록 하고 이 과정을 반복해 가장 많은 회의실을 배정할 수 있는 것을 선택하여 출력하면 된다고 가정했습니다.

그런데 실행 시간은 조건을 만족했으나 10문제 중 2문제만 통과했습니다. 알고리즘에서 적절한 시간을 선택하지 못한 것 같습니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
#define NONE -1
 
struct ConfTime 
{
    int roomNum;
    int begTime;
    int endTime;
};
 
int FindPossibleFitTime(const vector<ConfTime>& conferences, int pivot);
 
int main()
{
    int n;
    cin >> n;
 
    // 입력 개수만큼 기억공간 준비
    vector<ConfTime> conferences(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> conferences[i].roomNum
            >> conferences[i].begTime
            >> conferences[i].endTime;
    }
 
    vector<ConfTime> result;
    for (int i = 0; i < n; ++i)
    {
        int checkIndex{ i };
        vector<ConfTime> temp{ conferences[i] };
        while(true)
        {
            // 가자 적절한 입력을 찾는다.
            int fitIndex{ FindPossibleFitTime(conferences, checkIndex) };
            // 찾은 경우 해당 입력을 다음의 시작 위치로 가정하고 반복한다.
            if (fitIndex != NONE)
            {
                temp.push_back(conferences[fitIndex]);
                checkIndex = fitIndex;
            }
            // 불가능 하면 종료한다.
            else
            {
                break;
            }
        }
        // 가장 많은 회의를 열 수 있는 것을 선택한다.
        if (temp.size() > result.size())
        {
            result = temp;
        }
    }
 
    // 결과 출력
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); ++i)
    {
        cout << result[i].roomNum << ' ';
    }
    cout << endl;
}
 
int FindPossibleFitTime(const vector<ConfTime>& conferences, int pivot)
{
    int minDiffTime{ NONE };
    for (int j = 0; j < conferences.size(); ++j)
    {
        // 기준 시간의 끝 시간보다 시작 시간이 빠르면 무시한다.
        if (conferences[j].begTime < conferences[pivot].endTime)
        {
            continue;
        }
        // 처음 찾은 경우 바로 최적으로 넣는다.
        if (minDiffTime == NONE)
        {
            minDiffTime = j;
        }
        // 이전 최적값이 있으면 비교하여 더 적합한 것을 결정한다.
        else if (conferences[j].begTime < conferences[minDiffTime].endTime)
        {
            minDiffTime = j;
        }
    }
 
    return minDiffTime;
}

실패 결과를 살펴보니 단순히 시작 시간이 이전 회의의 끝 시간과 가깝다고 최적을 찾지는 못하고 있습니다.

추가적으로 회의가 끝나는 시간 또한 고려해야 할 것 같습니다.

회의의 지속 시간을 비교하기 위해 시간을 비교하는 것이 아닌 비교가 가능하도록 값을 만들어 내도록 하겠습니다.

이전 회의의 끝나는 시간과 비교할 회의의 시작시간의 차, 비교할 회의의 끝나는 시간과 시작시간의 차(지속 시간) 이 두 값의 합으로 비교하면 될 것 같습니다. 추가적으로 최초의 값을 따로 처리하지 않고 같은 알고리즘 내에서 처리되게 하겠습니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
#define NONE -1
 
struct ConfTime 
{
    int roomNum;
    int begTime;
    int endTime;
};
 
int FindPossibleFitTime(const vector<ConfTime>& conferences, int pivot);
int CalculateCompValue(const vector<ConfTime>& conferences, int pivot, int target);
 
int main()
{
    int n;
    cin >> n;
 
    // 입력 개수만큼 기억공간 준비
    vector<ConfTime> conferences(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> conferences[i].roomNum
            >> conferences[i].begTime
            >> conferences[i].endTime;
    }
 
    vector<ConfTime> result;
    for (int i = 0; i < n; ++i)
    {
        int checkIndex{ i };
        vector<ConfTime> temp{ conferences[i] };
        while(true)
        {
            // 가자 적절한 입력을 찾는다.
            int fitIndex{ FindPossibleFitTime(conferences, checkIndex) };
            // 찾은 경우 해당 입력을 다음의 시작 위치로 가정하고 반복한다.
            if (fitIndex != NONE)
            {
                temp.push_back(conferences[fitIndex]);
                checkIndex = fitIndex;
            }
            // 불가능 하면 종료한다.
            else
            {
                break;
            }
        }
        // 가장 많은 회의를 열 수 있는 것을 선택한다.
        if (temp.size() > result.size())
        {
            result = temp;
        }
    }
 
    // 결과 출력
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); ++i)
    {
        cout << result[i].roomNum << ' ';
    }
    cout << endl;
}
 
int FindPossibleFitTime(const vector<ConfTime>& conferences, int pivot)
{
    int minDiffTime{ NONE };
    int minCompValue{ 999999 };
    for (int j = 0; j < conferences.size(); ++j)
    {
        int newCompValue{};
 
        // 기준 시간의 끝 시간보다 시작 시간이 빠르면 무시한다.
        if (conferences[j].begTime < conferences[pivot].endTime)
        {
            continue;
        }
        // 그 외의 경우 비교할 수 있는 값을 만든다.
        else
        {
            newCompValue = CalculateCompValue(conferences, pivot, j);
        }
 
        // 각 비교값을 비교해 더 작은 것을 선택한다.
        if (newCompValue < minCompValue)
        {
            minDiffTime = j;
            minCompValue = newCompValue;
        }
    }
 
    return minDiffTime;
}
 
int CalculateCompValue(const vector<ConfTime>& conferences, int pivot, int target)
{
    // 이전 회의와 이 회의의 시작 시간 차이와
    // 이 회의의 지속시간을 기준으로 비교값을 만든다.
    return (conferences[target].begTime - conferences[pivot].endTime)
        + (conferences[target].endTime - conferences[target].begTime);
}

JUNGOL) 문제은행) 알고리즘) 회의실 배정