[알고리즘] 백준 1931번 "회의실 배정" (C/C++) - Don 임베디드

문제 요약:

한개의 회의식이 있는데, 이를 사용하려고 하는 회의 N개에 대하여 회의실 사용표를 만드는 프로그램이 필요하다.

각 회의는 시작 시간, 끝나는 시간 정보가 주어진다.

이때, 회의 시간이 겹치지 않게 하면서 최대 몇 개의 회의를 할 수 있는지 구해보자.

단, 회의는 시작하면 중간에 중단할 수 없으며, 하나의 회의가 끝나는 동시에 다음 회의가 시작할 수 있다.

하나의 회의의 시작시간과 끝나는 시간이 같을 수 있다. 이 경우는 시작하자마자 끝나는 것으로 생각한다.

 

제약:

1<= N <= 100000

N이 입력된 이후, 두번 째 줄부터 N+1줄 까지 각 회의의 시작 시간과 끝나는 시간이 주어진다.

시작 시간과 끝나는 시간은 (2^31 - 1) 보다 작거나 같은 자연수 또는 0 이다.

 

예제 1 입력.	예제 1 출력.
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14	4

 

정답코드:

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
class Meeting
{
public:
    int nStartTime;
    int nEndTime;
    Meeting(int nStartTime, int nEndTime) : nStartTime(nStartTime), nEndTime(nEndTime) {}
};
 
bool _Compare(Meeting m, Meeting n);
 
int main()
{
    int N;
    int nCurrentEndTime = 0;
    int nCountOfMeetings = 0;
    int nStartTime, nEndTime;
    vector<Meeting> v;    // stl 벡터 사용
 
    cin >> N;
 
    for(int i = 0; i < N; i++)
    {
        cin >> nStartTime >> nEndTime;
        v.push_back(Meeting(nStartTime, nEndTime));
    }
 
    // custom 비교함수 _Compare를 사용하여 회의 목록을 정렬한다.
    // 끝나는 시간이 빠른 순으로,
    // 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬.
    sort(v.begin(), v.end(), _Compare);
 
    // 끝나는 시간 순으로 정렬된 전체 목록을 하나씩 확인.
    for (int j = 0; j < static_cast<int>(v.size()); j++)
    {
        // 마지막으로 선택한 회의가 끝나는 시점과 현재 회의의 시작 시간을 비교.
        if (v.at(j).nStartTime >= nCurrentEndTime)
        {
            // 현재 회의 시작 시간이 마지막 회의가 끝난 시점과 같거나 뒤라면,
            // 현재 회의를 가능한 목록에 넣고 업데이트.
            nCountOfMeetings++;
            nCurrentEndTime = v.at(j).nEndTime;
        }
    }
 
    // 정답 출력.
    cout << nCountOfMeetings << endl;
 
    return 0;
}
 
bool _Compare(Meeting A, Meeting B)
{
    if (A.nEndTime == B.nEndTime)
    {
        // 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬.
        return (A.nStartTime < B.nStartTime);
    }
    else
    {
        // 끝나는 시간이 빠른 순으로,
        return (A.nEndTime < B.nEndTime);
    }
}

원본링크: https://www.acmicpc.net/problem/1931