[백준] 1931 회의실 배정 with C++

문제설명

---

입출력 예제

---

개념

　이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다.

---

풀이

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

int main()
{
    int N, n, k, count = 1;
    cin >> N;
    vector<meeting> v(N);

　회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k, 회의의 개수 count를 선언한다. 그리고 회의의 시작 시간과 종료 시간을 저장할 벡터 v를 초기화한다. 여기서 meeting 자료형은 다음과 같이 구조체로 정의하였다.

 

struct meeting
{
    int _start, _end;
};

　시작 시간을 _start, 종료 시간을 _end를 갖는 구조체다.

 

    for (int i = 0; i < N; ++i)
    {
        cin >> n >> k;
        v[i] = { n, k };
    }

    sort(v.begin(), v.end(), compare);
    int end_time = v[0]._end;

　벡터에 회의의 시작 시간과 종료 시간에 대한 정보를 삽입한다. 그 후 compare라는 기준으로 벡터를 정렬한 후, 겹치지 않는 시간을 판별하기 위한 end_time을 벡터의 첫 번째 원소의 end값으로 초기화한다.

 

bool compare(const meeting& a, const meeting& b)
{
    if (a._end == b._end)
        return a._start < b._start;

    else
        return a._end < b._end;
}

　가장 먼저 끝나는 회의를 선택하고, 그다음으로 빨리 끝나면서 이전에 선택한 회의와 시간이 겹치지 않도록 종료 시간을 기준으로 정렬을 하였다. 만약 종료 시간이 같다면 시작 시간이 빠른 순서로 정렬하였다.

 

    for (int i = 1; i < N; i++)
    {
        if (v[i]._start >= end_time)
        {
            count++;
            end_time = v[i]._end;
        }
    }

    cout << count;
}

　문제의 출력 조건에 맞게 count의 개수를 늘려주고, 최종적으로 count의 개수를 출력하면 된다. 여기서 count를 1로 미리 초기화한 이유는 첫 번째로 선택되는 회의를 미리 카운트하기 때문이다.

 

총합본

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

struct meeting
{
    int _start, _end;
};

bool compare(const meeting& a, const meeting& b)
{
    if (a._end == b._end)
        return a._start < b._start;

    else
        return a._end < b._end;
}

int main()
{
    int N, n, k, count = 1;
    cin >> N;
    vector<meeting> v(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> n >> k;
        v[i] = { n, k };
    }

    sort(v.begin(), v.end(), compare);
    int end_time = v[0]._end;

    for (int i = 1; i < N; i++)
    {
        if (v[i]._start >= end_time)
        {
            count++;
            end_time = v[i]._end;
        }
    }

    cout << count;
}