백준 11000번: 강의실 배정

문제링크 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 문제 설명  

 

강의갯수와 강의 진행 시간이 주어질때 필요한 최소 강의실 갯수는 ?

 

 알고리즘 

 

1. 강의진행시작시간이 빠른 순으로 정렬

2. 앞에서부터 강의 종료시간을 우선순위 큐에 넣고 차례대로

3. 우선순위큐의 top(진행중인 강의 종료시간) <= 현재 인덱스의강의 시작시간이 이면 top 을 pop 하고

   현재 인덱스 강의의 종료시간을 넣는다

4. 진행중인 강의  종료시간보다 현재 인덱스의 강의 시작시간이 작으면 그냥 넣는다

5. 마지막에 우선순위 큐의 사이즈를 cout 한다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int n;
    pair<int, int> p[200001];
    priority_queue<int, vector<int>, greater<int> > pq;
 
    cin >> n;
 
    for (int i = 0; i < n; ++i) {
        cin >> p[i].first >> p[i].second;
    }
 
    sort(p, p + n);
 
    pq.push(p[0].second);
 
    for (int i = 1; i < n; ++i) {
        if (pq.top() <= p[i].first) {
            pq.pop();
            pq.push(p[i].second);
        }
        else {
            pq.push(p[i].second);
        }
    }
 
    cout << pq.size() << endl;
 
    
}