11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)
www.acmicpc.net
처음엔 강의시간의 길이로 접근해야 된다고 생각했는데 결국 강의 종료시간과 다음 강의 시작시간을 비교하는 것이 중요하다는 것을 알게 되었다.
1. 각 강의들을 벡터에 저장하고 정렬해준다.
2. 각 강의의 종료시간을 우선순위 큐에 저장해주고 다음 강의들의 시작시간과 우선순위 큐의 top을 비교해준다.
3. 만 우선순위 큐의 top이 시작시간보다 작다면 강의실을 늘리고 아니면 종료시간을 pop해준다.
이런식으로 알고리즘을 생각하고 풀었으며 생각보다 다른 문제들과 좀 다른 유형이라 고민을 꽤 오래했다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int, int>> v;
int main() {
int n,x,y, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v.push_back({ x,y });
}
sort(v.begin(), v.end());
pq.push(v[0].second);
ans++;
for (int i = 1; i < n; i++) {
auto z = v[i];
if (z.first >= pq.top()) {
pq.pop();
}
else {
ans++;
}
pq.push(z.second);
}
cout << ans;
return 0;
}