[ BOJ / C++] 11000번 강의실 배정

8468 단어 bojcppboj

이번 문제는 pair와 우선순위 큐를 사용하여 해결했다.

  • n에 반복 횟수를 입력받는다.
  • pair에 각 강의의 시작 시간과 종료 시간을 입력 받는다.
  • 각 강의들을 시작 시간순으로 정렬시킨다.
  • 가장 처음 시작하는 강의의 종료 시간을 우선순위 큐에 넣는다.
  • 반복문을 통해 우선순위 큐의 top에 있는 값이 i번째 강의의 시작시간보다 작거나 같다면 우선순위 큐를 pop해주고 i번째 강의의 종료 시간을 push해준다.
  • 우선순위 큐의 top에 있는 값이 i번째 강의의 시작시간보다 크다면 i번째 강의의 종료 시간을 push해준다.(다른 강의실을 사용하는 것을 표현)
  • 최종적으로 우선순위 큐의 크기를 출력해준다.

Code

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 200001
using namespace std;

int n;
int a, b;
pair<int, int> p[MAX];
priority_queue<int, vector<int>, greater<int>> pq;
int classroom=0;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>p[i].first>>p[i].second;
    }
}

void Solution(){
    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);
        }
    }
    classroom=(int)pq.size();
    cout<<classroom<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}

좋은 웹페이지 즐겨찾기