[백준] 회의실 배정(C++)

문제링크

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

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	cin >> N;

    vector<pair<int, int>> meetings(N);

    for (int i = 0; i < N; ++i) 
    {
        cin >> meetings[i].first >> meetings[i].second;
    }

    // 끝나는 시간 기준 오름차순 정렬
    sort(meetings.begin(), meetings.end()
        , [](pair<int, int>& a, pair<int, int>& b){ 
            if (a.second == b.second) return a.first < b.first;
            return a.second < b.second;
        });

    int count = 0, last_end_time = 0;

    for (const auto& meeting : meetings) 
    {
        if (meeting.first >= last_end_time) 
        {
            last_end_time = meeting.second;
            count++;
        }
    }

    cout << count << '\n';
    return 0;
}

 

 

해결 방법

끝나는 시간을 기준으로 오름차순으로 정렬 후, 이전 회의 종료시간보다 같거나 늦게 시작하는 회의를 선택한다.