[ BOJ / C++] 11000번 강의실 배정
이번 문제는 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;
}
#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;
}
Author And Source
이 문제에 관하여([ BOJ / C++] 11000번 강의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-11000번-강의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)