[BOJ] 백준_11000번_강의실 배정_C/C++백준 알고리즘2022. 1. 21. 20:00
목차
문제 출처
https://www.acmicpc.net/problem/11000
문제 설명
코드
//[BOJ] 11000번 강의실 배정
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm> //sort 함수 사용
using namespace std;
vector <pair<int, int>> start_end;
priority_queue<int, vector<int>, greater<int>> end_queue;
int cls_asg(int n)
{
end_queue.push(start_end[0].second);
for (int i = 1; i < n; i++)
{
end_queue.push(start_end[i].second); //강의실 개수 추가
if (end_queue.top() <= start_end[i].first) //만약 top의 종료 시간이 새로 push된 시작 시간보다 작거나 같을 경우
end_queue.pop(); //pop시키면서 push된 큐의 강의실 개수를 유지(증가x)
}
return end_queue.size();
}
int main()
{
cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
int n, s, t;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s >> t;
start_end.push_back(make_pair(s, t));
}
sort(start_end.begin(), start_end.end());
cout << cls_asg(n) << "\n";
}
풀이 과정
시작 시간과 종료 시간, 두 가지를 쌍으로 받아야 하므로 pair를 사용해 start_end에 first에는 시작 시간을, second에는 종료 시간을 입력받는다. n번 입력받은 후에는 시작 시간에 따라 오름차순으로 정렬한다. 비교 함수에 greater<int>를 넣어 오름 차순으로 정렬되는 우선순위 큐 end_queue를 만든다. 이 큐는 종료 시간만 들어가는 큐이다. 우선 start_end에 가장 첫번째 있는 종료 시간(start_end[0].second)을 push 한다. 0번 인덱스 값을 넣었으니 이후 for문에는 1번 인덱스부터 i가 n보다 작을 때 까지 i를 증가시키며 end_queue에 start_end의 i번 인덱스 종료 시간을 push 하고 만약 end_queue에 가장 먼저 push된 원소의 종료 시간이 i번 인덱스 start_end의 시작 시간보다 작거나 같을 경우 수업 시간이 겹치지 않는다는 뜻이므로 강의실을 추가하지 않을 것이고 해당 end_queue는 pop을 시켜줌으로서 강의실의 개수를 유지한다. 과정을 마치고 남은 end_queue의 사이즈가 최소한의 강의실 사용 개수이다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_5585번_거스름돈_C/C++ (0) | 2022.01.23 |
---|---|
[BOJ] 백준_22864번_피로도(재채점)_C/C++ (0) | 2022.01.22 |
[BOJ] 백준_1049번_기타줄_C/C++ (2) | 2022.01.19 |
[BOJ] 백준_2864번_5와 6의 차이_C/C++ (0) | 2022.01.12 |
[BOJ] 백준_2217번_로프_C/C++ (0) | 2022.01.10 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!