📌 알고리즘 - 백준 1931번 회의실 배정 문제풀이

문제

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

문제풀이

회의의 최대 개수를 구하기 위해서 전체 $N$개의 회의들을 회의가 끝나는 시간 순서로 정렬한다. 가장 빨리 끝나는 회의를 ans 벡터에 포함시킨 후, 회의 시작시간이 ans의 마지막 회의의 끝나는 시간과 같거나 나중에 시작할 경우 ans에 포함시킨다.

$N$개의 회의를 순회한 후 ans 벡터의 크기가 답이다.
$O(N)$으로 답을 구할 수 있다.

코드

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int N;
vector<pair<int, int>> v, ans;

void Input() {
    cin>>N;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin>>start>>end;
        v.push_back({end, start});
    }
}

void Solution() {
    sort(v.begin(), v.end()); // 끝나는 시간 순으로 정렬
    ans.push_back(v[0]);
    for (int i = 1; i < v.size(); i++) {
        int end = ans[ans.size()-1].first; // 마지막 회의가 끝나는 시간
        if (v[i].second >= end) ans.push_back(v[i]);
    }
    cout<<ans.size()<<endl;
}

void Solve() {
    Input();
    Solution();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Solve();

    return 0;
}