[백준-cpp] 1931. 회의실 배정

1. 문제핵심

• n개의 회의 일정이 주어진다. (시작시간, 종료시간)
• 회의가 겹치지 않게 일정을 정렬할 때 최대 몇 개 회의일정을 정할 수 있을까
• 일정을 잡는 규칙은 현재 회의 종료 시간 <= 다음 회의 시작 시간
• 최대한 일정을 많이 잡기 위한 규칙 빨리 시작하고 빨리 끝나는 회의 먼저 일정을 잡는다.

 

2. 해결

#include <bits/stdc++.h>

using namespace std;

int n;
vector<pair<int, int>> meetings;

bool compare(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;

    return a.second < b.second;
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;

    while (n--)
    {
        int start, end;
        cin >> start >> end;
        meetings.push_back({start, end});
    }

    sort(meetings.begin(), meetings.end(), compare);

    int cnt = 0;
    int end = -1;

    for (auto m : meetings)
    {
        if (end > m.first)
            continue;

        end = m.second;
        cnt++;
    }

    cout << cnt << '\n';

    return 0;
}