사용자의 컴퓨터 시작 시간과 끝 시간이 주어진다.
사용자는 비어있는 자리중 가장 작은 번호부터 사용한다.
컴퓨터를 최소한으로 사용할 때 그 개수와 자리별 사용회수를 구하는 문제이다.
우선순위 큐로 해결 할 수 있다.
사용자를 시작시간 순으로 정렬시킨 후 우선순위 큐에서 종료되어 나오는 사용자들을 관리해 준다.
set으로 종료되어 나오는 사용자들의 자리 번호를 관리해주면 된다.
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
int N;
pair<int, int> p[100001];
set<int> save;
int ans[100001];
int solve() {
priority_queue<pair<int, int>> pq;
int size = 0;
for (int n = 0; n < N; n++) {
while (!pq.empty()) {
if (-pq.top().first <= p[n].first) {
save.insert(pq.top().second);
pq.pop();
}
else break;
}
if (save.empty()) {
pq.push({ -p[n].second, size });
ans[size++]++;
}
else {
auto idx = save.begin();
pq.push({ -p[n].second, *idx });
ans[*idx]++;
save.erase(idx);
}
}
return size;
}
int main() {
scanf("%d", &N);
for (int n = 0; n < N; n++) scanf("%d%d", &p[n].first, &p[n].second);
sort(p, p + N);
int M = solve();
printf("%d\n", M);
for (int m = 0; m < M; m++) printf("%d ", ans[m]);
return 0;
}
| cs |
