[C++] 백준 11000번: 강의실 배정

🔗 문제

11000번: 강의실 배정

11000번: 강의실 배정

 

🖍 풀이

 

✔️ 최적의 해 구하는 방법
 한 강의실에 최대한 많은 강의를 해야 한다.

 

강의 시간이 담긴 벡터를 정렬하는 이유

시작 시각 정렬을 하면 한 강의실을 쓸 수 있는지 연속해서 판단이 가능하기 때문이다.

 

우선 순위 큐를 사용하는 이유

 

아래 예시는 (1, 7), (7, 10)과 (2,3), (3, 4), (4, 8) 강의를 묶어 최소 2개의 강의실을 사용할 수 있다.

5
1 7
2 3
3 4 
4 8
7 10

 

(1, 7), (2, 3)이 같은 강의실은 같은 강의실을 못 쓴다는 사실을 알아냈다면 (1, 7) 과 (3, 4) → (1, 7)과 (4, 8) … 를 확인하는 것보다 앞선 강의(1, 7)를 다음으로 빨리 시작하는 (2, 3)로 바꿔 연속적으로 판단하는게 더 낫다.

 

내부에서 원소들을 정렬하는 특성이 있고 정렬방법도 선택 가능하기 때문에 priority_queue를 사용해서 푼다.

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

 

 

 

std::sort(v.begin(), v.end());

pq.push(v[0].second);

for (int i=1; i<N; ++i)
{
    if (pq.top() <= v[i].first)
        pq.pop();
    pq.push(v[i].second);

이게 이해가 가지 않으면 pq와 pq.top 그리고 v[i].first를 종이에 그려가며 이해하는 걸 추천한다. 글로는 장황해지기만 하지 설명이 잘 되지 않는다. ㅠㅠ

 

 

std::cout << pq.size(); // answer

우선순위 큐에는 각 강의실의 마지막 강의시간만 남게 되고 그 개수가 최소 강의실 개수다.

 

 

💾  소스

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

int main()
{
    int N, start, end;
    std::vector<std::pair<int, int>> v;
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> start >> end;
        v.push_back({start, end});
    }
    
    std::sort(v.begin(), v.end());

    pq.push(v[0].second);

    for (int i=1; i<N; ++i)
    {
        if (pq.top() <= v[i].first)
            pq.pop();
        pq.push(v[i].second);
    }

    std::cout << pq.size();
    
    return 0;
}