[백준/BOJ] 백준 12764번 : 싸지방에 간 준하

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

12764번: 싸지방에 간 준하

priority_queue<tuple<int, int, int>> pq (-시간,사용자번호, 시작인지 종료인지(0:시작, 1:종료))를 저장하는 우선순위 큐와, priority_queue<int> can_use_com (-사용 가능한 컴퓨터 번호)를 저장하는 우선순위 큐를 만들어 문제를 해결했다.

 

코드

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

int n;
vector<int> com(100001, 0);
vector<pair<int, int>> user; //해당 사용자의 종료시간
vector<int> user_com(100001, 0); //해당 사용자가 사용하는 컴퓨터
int com_number = 1;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	priority_queue<tuple<int, int, int>> pq; //(-시간,사용자번호, 시작인지 종료인지(0:시작, 1:종료))
	priority_queue<int> can_use_com; //(-사용가능한 컴퓨터 번호)

	for (int i = 0; i < n; i++)
	{
		int p, q;
		cin >> p >> q;

		user.push_back(make_pair(p, q));
	}

	for (int i = 0; i < user.size(); i++)
		pq.push(make_tuple(-user[i].first, i, 0));

	for (int i = 1; i <= n; i++)
		can_use_com.push(-i);

	while (!pq.empty())
	{
		int here_time = -get<0>(pq.top());
		int here_user = get<1>(pq.top());
		int here_start_end = get<2>(pq.top());
		pq.pop();

		//시작일때
		if (here_start_end == 0)
		{
			int here_use_com = -can_use_com.top();
			can_use_com.pop();

			user_com[here_user] = here_use_com; //현재 사용자가 사용하는 컴퓨터 저장
			com[here_use_com]++; //해당 컴퓨터 이용 수 증가

			pq.push(make_tuple(-user[here_user].second, here_user, 1)); //해당 사용자의 종료
		}

		//종료일때
		else
		{
			int here_use_com = user_com[here_user];
			can_use_com.push(-here_use_com); //해당 사용자가 사용했던 컴퓨터 사용 가능
		}
	}

	int com_cnt = 0;

	for (int i = 0; i < n; i++)
		com_cnt = max(com_cnt, user_com[i]);

	cout << com_cnt << "\n";

	for (int i = 1; i <= com_cnt; i++)
		cout << com[i] << " ";

	return 0;
}