👓 문제 설명
서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.
💣 제한 사항
- 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다.
- 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.
- 첫째 줄에 최소 회의실 개수를 출력한다.
🚨 접근 방법
주어진 예제는 다음과 같다.
3
0 40
15 30
5 10
우선 시작시간이 빠른 순서부터 회의를 진행해야한다.
이후 다음 순서의 회의를 진행할 때 앞서 진행 중이었던 회의가 끝났는지 확인을 한다.
만약 끝났다면 그 회의실을 그대로 사용하고,
끝나지 않았다면 새로운 회의실을 배정해 주어야한다.
1번 회의실 (0 시작 40 끝)
2번 회의실 (5 시작 10 끝 -> 대기 -> 15 시작 30 끝)
이렇게 말이다.
이를 위해서 우선
벡터로 입력 값을 받은 후
시작 시간이 빠른 순서부터 정렬한다.
이후 우선순위 큐에
시작 시간이 빠른 회의의 종료 시간을 넣는다.
만약 현재 우선순위 큐의 top의 값 (이전에 진행 중이던 회의의 종료 시간) 보다 현재 시작되어야 할 회의의 시작시간이 더 크면
-> 이전 회의 종료이므로 이전에 사용하던 회의실 그대로 사용 가능
우선 순위 큐를 pop한다.
마지막으로 남아있는 우선 순위 큐의 크기는 즉, 사용한 회의실의 개수이다.
🚈 풀이
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n;
vector<pair<int,int>>v;
void func() {
int ans = 0;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
v.push_back({ s,e });
}
sort(v.begin(), v.end());
priority_queue<int,vector<int>,greater<int>>pq;
pq.push(v[0].second);
for (int i = 1; i < n; i++) {
// 다음 회의 시작 시간보다 현재 회의 종료시간이 빠르면
// 끝난 회의이므로 pop
while (!pq.empty() && pq.top() <= v[i].first)pq.pop();
pq.push(v[i].second);
ans = max(ans, (int)pq.size());
}
cout << ans;
}
int main() {
cin >> n;
func();
return 0;
}