11000번 강의실 배정

※ 아래 문제도 풀어보자.(회의실 개수 최댓값 구하기)

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

 

 

 

 

 

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

 

강의실 개수 최솟값을 구하는 문제이다.

시작시간 기준으로 오름차순 정렬한다.

우선순위 큐를 활용하여, 종료시간을 넣어주면서 시작시간을 활용한다.

 

 

 

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> v;

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d", &N);

    int S, T;
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &S, &T);
        v.push_back({ S, T });
    }

    // S를 기준으로 오름차순
    sort(v.begin(), v.end());

    priority_queue<int> pq;

    for (auto i : v) {
        if (pq.empty()) {
            pq.push(-i.second);
            continue;
        }
        if (i.first < -pq.top()) {
            // 먼저 진행한 강의의 종료시간(-pq.top())이
            // 바로 이어서 진행할 강의의 시작시간(i.first)보다
            // 크다면, 아직 강의가 안 끝났으므로, pq에 push한다.
            // 즉, 강의실 1개 추가.
            pq.push(-i.second);
        }
        else {
            // 문제 조건에 의하여
            // 수업이 끝난 직후에 다음 수업을 시작할 수 있으므로(Ti ≤ Sj),
            // 다시 말하면, 강의실 1개로 바로 이어서 수업을 시작할 수 있으므로,
            // 먼저 진행했던 강의를 끝내고(pq.pop()),
            // 이어서 바로 다음 수업을 진행한다.(pq.push(-i.second))
            // 강의실의 수는 변함이 없다.
            pq.pop();
            pq.push(-i.second);
        }
    }

    printf("%d\n", pq.size());

    return 0;
}