백준 1931 회의실 배정 : C++

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

1931번: 회의실 배정

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

using namespace std;

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

    long long t1,t2;
    vector<vector<long long>> v;
    vector<long long> tmp;

    for(int i = 0; i < n; i++){
        cin >> t1 >> t2;
        // 처음부터 반대로 push
        tmp.push_back(t2);
        tmp.push_back(t1);
        v.push_back(tmp);
        tmp.clear();
    }
    sort(v.begin(), v.end());

    // 가장 빨리 끝나는 t2를 찾고
    // t2와 일치 혹은 더 큰 t1을 은 다음 (정렬되어있으니 복수요소들 비교할 필요 x)

    long long end = v[0][0];
    int count = 1;
    for(int i = 1; i < n; i++){
        if(v[i][1] >= end){
            count++;
            end = v[i][0];
        }
    }

    cout << count;
}

 

t1 : 회의 시작시간

t2 : 회의 끝나는 시간

 

먼저 입력받은 회의 시간표를 회의가 일찍 끝나는 순으로 정렬한다.

회의가 가장 일찍 끝나는 요소부터 시작, 회의가 끝난 시간과 동일하거나 더 늦게 "시작"하는 회의를 찾아 탐색.

백준 입력 예시