[1931] 회의실 배정 (C++)

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

using namespace std;

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

    int N; cin >> N;
    vector<pair <int, int>> A(N);
    int cnt = 0; int end = -1;

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

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

    for (int i = 0; i < N; i++) {
        if (A[i].second >= end) {
            end = A[i].first;
            cnt++;
        }
    }

    cout << cnt;    

    return 0;
}

 

1. 회의가 시작되는 시간이 빨라도 종료가 늦으면 회의의 수는 최대가 될 수 없다

=> 따라서 회의 종료 시간이 빠른 순서대로 정렬하기 위해 first에 종료 시간을, second에 시작 시간을 저장한다

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13

 

2. 가장 먼저 종료되는 회의를 탐색한 후, 시간이 겹치지 않으며 가장 일찍 끝나는 회의를 탐색한다

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13