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

www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 

 

알고리즘 종류

자료구조

우선순위 큐

 

 

 

사고 과정

1. 강의실을 배정하기 위해서 시작 시간을 기준으로 오름차순 정렬을 합니다.

 

2. 수업 시간을 하나씩 가져옵니다. 현재 수업의 시작 시간이 이전 수업의 끝나는 시간보다 크다면 빈 강의실이므로 우선순위 큐(pq)에서 꺼냅니다. 꺼낸 강의실 번호를 저장합니다.

 

3. 빈 강의실이 있다면, 그 곳에 현재 수업을 배정합니다. 빈 강의실이 없다면, 강의실을 하나 추가합니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n;
int ans=0;
 
vector<pair<int, int> > v;
priority_queue<pair<int, int> > pq; // 끝나는 시간, 강의실 번호  
priority_queue<int> room; // 빈 강의실  
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int a, b;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        v.push_back({a, b});
    }
    
    sort(v.begin(), v.end());
    
    // 강의실 배정  
    for(int i=0; i<n; i++){
        int front = v[i].first;
        int end = v[i].second;
        
        while(!pq.empty()){ // 현재 강의실 시작 시간이 다른 강의실의 끝나는 시간보다 크면 뽑기  
            if(-pq.top().first > front) break;
            room.push(pq.top().second);
            pq.pop();
        }
        
        // 뽑았을 때, 빈 강의실이 있으면 넣기  
        if(!room.empty()){
            pq.push({-end, room.top()});
            room.pop();
        }
        // 뽑았을 때, 빈 강의실이 없으면 강의실 추가  
        else{
            ++ans;
            pq.push({-end, ans});
        }
    }
    
    cout << ans << endl;
}

 

 

 

시행착오