문제

문제 링크

해설

• 회의실을 최대한 사용하기 위해서는 더 빨리 시작하고 더 빨리 끝나는 회의를 고르는 것이 유리하다는 것을 알 수 있습니다.
• 따라서 빨리 시작하는 것을 알기 위해서는 모든 회의를 시작시간에 대해 오름차순으로 정렬 sort() 해야 합니다.
• 예제를 예를 들어, 이 문제에서 가장 까다로운 점은 (0, 6)과 (1, 4)에서 후자를 고르는 판단조건을 세우는 것입니다.
  • (0, 6)은 더 빨리 시작하지만, (1, 4)는 더 빨리 끝나기 때문입니다.
  • 하지만, 최대한 많은 회의를 고르기 위해서는 시작시간 보다는 더 빨리 끝나는 회의를 고르는 것을 고르는 것이 더 유리합니다.
  • 따라서 여기서는 (1, 4)를 고르는 것이 맞습니다.
• 저는 stack<> 스택 자료구조를 사용했습니다.
  1. 스택의 push() 조건을 결정합니다.
     • 스택이 비어있을 때
     • 스택의 top()보다 현재 회의실이 더 빨리 끝날 때
     • 스택의 top() 이후에 회의실을 사용할 수 있을 때
  2. 위 3가지 조건 중 1, 3번은 무조건 push()고, 2번은 pop()을 한 뒤 push() 합니다.
• 예제를 예로 들어 위 로직을 적용해봅시다.
  1. 스택이 비어있으므로 (0, 6) push.
  2. 스택의 top인 (0, 6)보다 (1, 4)가 빨리 끝나므로 pop한 뒤 push.
  3. (2, 13), (3, 5), (3, 7)은 top과 겹치며 늦게 끝나므로 무시합니다.
  4. 스택의 top인 (1, 4) 이후에 (5, 7)을 사용할 수 있으므로 push.
  5. (5, 9), (6, 10)은 top과 겹치며 늦게 끝나므로 무시합니다.
  6. 스택의 top인 (5, 7) 이후에 (8, 11)을 사용할 수 있으므로 push.
  7. 스택의 top인 (8, 11)이후에 (12, 14)를 사용할 수 있으므로 push.
  8. 결과적으로 (1, 4) ⇢ (5, 7) ⇢ (8, 11) ⇢ (12, 14)로 최대 4개의 회의실을 사용할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    uint N;
    cin >> N;
    vector<pair<uint, uint>> vec;
    for (uint i = 0; i < N; ++i) {
        int s, e;
        cin >> s >> e;
        vec.emplace_back(s, e);
    }
    sort(begin(vec), end(vec));

    stack<pair<uint, uint>> stk;
    for (size_t i{0}, sz{vec.size()}; i < sz; ++i) {
        if (stk.empty() || stk.top().second <= vec[i].first) stk.emplace(vec[i]);
        else if (stk.top().second > vec[i].second) stk.pop(), stk.emplace(vec[i]);
    }
    cout << stk.size() << '\n';
}

소스코드 링크

결과