https://www.acmicpc.net/problem/19598
<코드>
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
priority_queue<int,vector<int>,greater<int>>result;
for(int i=0;i<n;i++)
{
int s,e;// 시작 시간, 끝나는 시간
cin>>s>>e;
pq.push(make_pair(s,e));
}
result.push(pq.top().second);
pq.pop();
while(!pq.empty())
{
if(result.top()<=pq.top().first)
{
result.push(pq.top().second);
result.pop();
}
else
{
result.push(pq.top().second);
}
pq.pop();
}
cout<<result.size();
}
<풀이 과정>
이 문제는 강의실 1374와 같은 문제이다.
https://www.acmicpc.net/problem/1374
우선순위 큐를 통해 시작 시간이 빠른 순서대로 pq에 삽입시켜준다.
그리고 임의의 강의를 result 큐에 넣어준다. 만약 다른 회의의 시작 시간이 result의 강의의 종료시간보다 크거나 같으면(왜냐하면 시작시간과 종료시간이 동일해도 무관하기 때문이다) 회의를 추가함과 더불어 pop해주면 되고,
그렇지 않으면 회의실을 하나 추가해주면 된다.
'PS > 그리디 알고리즘[Greedy]' 카테고리의 다른 글
1049 기타줄(c++) (0) | 2022.07.21 |
---|---|
1202 보석 도둑(c++) (0) | 2022.07.20 |
백준 13975 파일 합치기 3(c++) (0) | 2022.07.19 |
백준 4889 안정적인 문자열(c++) (0) | 2022.07.17 |
백준 1758 알바생(c++) (0) | 2022.07.17 |