[Baekjoon] 1931: 회의실 배정 - (C3, G5) Sorting, Greedy Method

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

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

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

1931번: 회의실 배정

 

문제 해결을 위해서는 어떤 회의를 먼저 선택해야 할지 그 기준을 정해야 한다. 가장 많은 회의를 선택하기 위해서는, 회의의 종료 시각이 빨라야 한다. 예를 들어, 종료 시각이 4시인 회의와 9시인 회의가 있다면 4시인 회의를 선택하는 것이 더 많은 회의를 진행할 가능성이 높을 것이다. 

 

따라서 종료 시간이 빠른 순으로 회의를 정렬한 후, 시작 시간이 종료 시간보다 빠르거나 같다면 그 회의를 선택하여 회의 개수를 업데이트한다. 

 

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

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int, int>> meetings;

    while (N--)
    {
        int start, end;
        cin >> start >> end;
        meetings.emplace_back(start, end);
    }

    // 종료 시간 기준으로 정렬 (종료 시간이 같으면 시작 시간 기준 정렬)
    sort(meetings.begin(), meetings.end(), [](const pair<int, int> &a, const pair<int, int> &b)
         {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second; });

    /* 정렬 debug 코드
    for (const pair<int, int> &r : meetings)
    {
        auto [s, e] = r;
        cout << s << " " << e << '\n';
    }
    */

    // 최대 회의 수 계산
    int max_count = 0;
    int last_end_time = 0;

    for (const auto &[start, end] : meetings)
    {
        if (start >= last_end_time)
        {

            /* debug 코드
            cout << start << " " <<end<<" -> ";
            */
            max_count++;
            last_end_time = end; // 현재 회의의 종료 시간을 갱신
        }
    }

    cout << max_count;
    return 0;
}

emplace_back 함수는 컨테이너 내부에서 객체를 직접 생성하여 추가한다. 객체를 생성하는 데 필요한 인수를 전달하여 직접 생성하므로 불필요한 복사/이동 연산을 생략할 수 있다.