1931번 - 회의실배정(c++)

🗒 1931번 문제

📌 재정렬한 순서대로 최대 회의의 개수를 찾자 ❗️

1️⃣ 받아온 시작 시간과 종료 시간을 Vector를 통해서 받는다.
-> 종료 시간을 기준으로 정렬하기 위해서 종료 시간부터 받아온다.

2️⃣ sort함수를 통해서 vector를 정렬
-> queue의 경우에는 begin(), end()를 사용할 수 없기에 vector를 사용하면 정렬이 좀 더 편리

3️⃣ vector로 받아온 순서를 queue에 넣고 겹치는 순서는 빼고 이어지는 최대 순서를 찾는다

4️⃣ 현재 종료 시간보다 그 다음 시작 시간이 작으면 그 다음 회의실로는 적합하지 않기 때문에 queue에서 빼기

5️⃣ while문 조건에 맞지 않으면 다음 회의 시간으로 적합하기에 cnt의 수를 올리기

➰ 코드로 나타낸 1931번 ➰

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

using namespace std;

int main() {
    int num, cnt = 0;
    vector<pair<int, int>> time;
    queue<pair<int, int>> que;
    
    cin >> num;
    
    // 시간을 종료, 시작 순으로 넣어주기
    for (int i = 0; i < num; i++) {
        int startT, endT;
        cin >> startT >> endT;
        time.push_back(make_pair(endT, startT));
    }
    
    // vector 정렬
    sort(time.begin(), time.end());
    
    for (int i = 0; i < num; i++) {
        que.push(make_pair(time[i].first, time[i].second));
    }
    
    // 최대 회의실 수 세기
    while (!que.empty()) {
        int first = que.front().first;
        que.pop();
        cnt++;
        if (que.empty()) break;
        while (first > que.front().second) {
            que.pop();
            if (que.empty()) break;
        }
    }
    
    cout << cnt << endl;
}