12764 싸지방에 간 준하

12764 싸지방에 간 준하 https://www.acmicpc.net/problem/12764

사용자의 컴퓨터 시작 시간과 끝 시간이 주어진다.
사용자는 비어있는 자리중 가장 작은 번호부터 사용한다.
컴퓨터를 최소한으로 사용할 때 그 개수와 자리별 사용회수를 구하는 문제이다.

우선순위 큐로 해결 할 수 있다.
사용자를 시작시간 순으로 정렬시킨 후 우선순위 큐에서 종료되어 나오는 사용자들을 관리해 준다.
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; } Colored by Color Scripter

cs