[BOJ 12764] 싸지방에 간 준하(c++)

https://www.acmicpc.net/problem/12764

 

문제 개요

N명의 사람이 정해진 시간에 싸지방을 이용할 때, 모든 사람이 기다리지 않고 이용할 수 있는 최소 컴퓨터 개수와 각 자리별 사용 인원을 구하는 문제입니다. 다음의 규칙을 따릅니다.

 

• 비어있는 자리 중 가장 작은 번호의 자리에 앉음
• 시작/종료 시각이 겹치지 않음

(1 ≤ N ≤ 100,000)

(0 ≤ P < Q ≤ 1,000,000)

---

 

문제 풀이

이 문제는 회의실 배정 문제의 변형으로, 우선순위 큐를 활용한 그리디 알고리즘으로 해결하였습니다.

1. 시작 시간 기준으로 사람들을 정렬
2. 사용 중인 컴퓨터를 종료 시간 기준 최소 힙으로 관리
3. 비어있는 컴퓨터 번호를 최소 힙으로 관리
4. 새로운 사람이 올 때:
   • 종료된 컴퓨터들을 사용 가능 목록에 추가
   • 사용 가능한 컴퓨터 중 가장 작은 번호 할당
   • 없으면 새 컴퓨터 추가

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, cnt;
vector<pair<int, int>> arr;
vector<int> res;

class pc {
public:
	int et, num;
	bool operator < (const pc& other) const {
		return et > other.et;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	arr.reserve(n);
	res.reserve(n / 2);
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		arr.push_back({ x, y });
	}
	sort(arr.begin(), arr.end());
	priority_queue<pc> pq;
	priority_queue<int> pc_use;
	for (auto cur : arr) {
		while (!pq.empty()) {
			if (pq.top().et < cur.first) {
				pc_use.push(-pq.top().num);
				pq.pop();
			}
			else {
				break;
			}
		}
		int pn;
		if (pc_use.empty()) {
			pn = cnt++;
			res.push_back(1);
		}
		else {
			pn = -pc_use.top();			
			res[pn]++;
			pc_use.pop();
		}
		pq.push({ cur.second, pn });
	}
	cout << cnt << '\n';
	for (int r : res) {
		cout << r << ' ';
	}
	return 0;
}