[백준/그리디/C++] 11000번 강의실 배정(우선순위큐 사용) *

문제는 여기!

우선순위 큐

// 가장 작은 값이 우선순위가 되는 큐 (오름차순)
priority_queue<int, vector<int>, greater<int> > pq_less;

// 가장 큰 값이 우선순위가 되는 큐 (내림차순)
priority_queue<int, vector<int>, less<int> > pq_greater;

// 삽입
pq_less.push(0);

// 우선순위가 가장 높은 요소 반환
pq_less.top();
 
//우선순위가 가장 높은 요소 제거
pq_greater.pop();

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> classTime; // 수업시간 목록
priority_queue<int, vector<int>, greater<int>> pq_less; // 종료시간 큐(가장 작은 값이 우선순위가 되는 큐)

int greedy(int cnt){
    pq_less.push(classTime[0].second); // 첫번째 수업의 종료시간을 pq에 삽입

    // 필요한 강의실 선택
    for(int i=1; i<cnt; i++){
        // i번째 수업의 종료시간을 pq에 삽입
        pq_less.push(classTime[i].second);
        // top의 종료시간보다 i번째 수업이 늦게 시작하면 같은 강의실에서 진행가능
        if(pq_less.top() <= classTime[i].first){
            // 기존의 top 제거
            pq_less.pop();
        }
    }
    return pq_less.size();
}

void input() {
    cin >> N;
    for(int i=0; i<N; i++){
        int start, end;
        cin >> start >> end;
        classTime.push_back({start, end});
    }
    sort(classTime.begin(), classTime.end()); // 시작시간으로 정렬
}

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

    input();
    cout << greedy(N);

    return 0;
}

 

운호님 블로그 참고!