[11000번] 강의실 배정

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐

우선순위 큐를 이용하여 문제를 해결 할 수 있다.

우선 입력 자체가 어떻게 들어올지 모르니 오름차순 정렬을 해준 후 문제를 해결해본다.

 pq는 수업이 끝나는 시간을 기준으로 pq를 형성해준다.

1. pq에 아무 값이 없는경우(수강신청을 처음 하는경우) :: 그냥 값을 넣어준다.

2. pq에 값이 있을 때, pq의 가장 빨리 끝나는 수업 시간과 현재 보고있는 시작하는 수업 시간을 비교하여

끝나고 난 후, 시작할 수 있는 수업이 있다면 pq의 top값은 pop을 하고 현재 값을 push해준다.

3. 그 외의 경우에는 수업실을 추가해야하는 경우이므로 push해준다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <queue> #include <functional>   using namespace std;   typedef pair<int, int> pii;   vector<pii> vc;   priority_queue<pii, vector<pii>, greater<> > pq;   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int a, b;         scanf("%d %d", &a, &b);           vc.push_back({ a,b });     }       sort(vc.begin(), vc.end());       for (int i = 0; i < vc.size(); i++)     {         int first = vc[i].first;         int last = vc[i].second;           if (pq.empty())             pq.push({ last, first });           else if (pq.top().first <= first)         {             pq.pop();             pq.push({ last, first });         }         else             pq.push({ last, first });     }       cout << pq.size();     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus