BOJ - 1931 회의실 배정

회의 시간이 겹치지 않도록 하여 최대한 많은 회의를 진행하도록 하는 문제이다.

문제풀이 전략
시간이 겹치지 않게 하며 최대한 많은 회의를 회의실에 배정해야 한다.

시간이 겹치는지 확인하기 위해서는 이전 회의의 끝시간과 다음 회의의 시작 시간을 보면 된다.

끝 시간 기준으로 정렬한 후 빨리 끝나는 회의부터 차례로 비교하여 순회하면 충분히 풀 수 있는 문제이다.

코드

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

using namespace std;
int main() {
    int n;
    cin >> n;

    vector<pair<int,int>> v;
    for(int i=0;i<n;i++){
        int s;
        int e;
        cin >> s >> e;
        v.push_back(make_pair(e,s));
    }

    sort(v.begin(), v.end());

    int cnt = 0;
    int end = -1;
    for(int i=0;i<v.size();i++){
        if(v[i].second >= end){
            end = v[i].first;
            cnt++;
        }
    }
    cout << cnt << "\n";

    return 0;
}

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