https://www.acmicpc.net/problem/11000
풀이
우선순위 큐와 vector를 이용하였다.
vector에 시작시간과 종료시간을 넣은 후 오름차순으로 정렬한다.
이후 우선순위 큐에 오름차순으로 정렬된 종료시간을 저장하고, 이후 종료시간과 두번째 저장된 시작시간을 비교한다.
종료 시간보다 시작시간이 작은 경우는, 다른 강의실을 사용해야하기에 우선순위 큐에 넣어주고,
예외 상황에는 동일 강의실을 쓰기에, pop 이후 다시 push를 해준다.
Code
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<pair<int, int>> time(N);
for (int i = 0; i < N; i++)
cin >> time[i].first >> time[i].second;
sort(time.begin(), time.end());
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(time[0].second);
for (int i = 1; i < N; i++)
{
if (time[i].first < pq.top())
pq.push(time[i].second);
else
{
pq.pop();
pq.push(time[i].second);
}
}
cout << pq.size();
}
'💻 OnlineJudge > Baekjoon' 카테고리의 다른 글
[백준 / BOJ] C++ 2178 미로 탐색 (0) | 2022.10.17 |
---|---|
[백준 / BOJ] C++ 1260 DFS와 BFS (0) | 2022.10.14 |
[백준 / BOJ] C++ 2075 N번째 큰 수 (0) | 2022.10.12 |
[백준 / BOJ] C++ 7662 이중 우선순위 큐 (0) | 2022.10.12 |
[백준 / BOJ] C++ 1715 카드 정렬 (0) | 2022.10.06 |