문제 풀이

하나는 사용 중인 컴퓨터의 끝나는 시간과 그 컴퓨터의 번호의 정보를 가지고 있는 큐와, 지금 사용 중이지 않은 컴퓨터의 번호의 정보를 갖는 두 개의 우선순위 큐를 사용하여 문제를 해결한다.
처음 입력받은 데이터들을 오름 차순으로 정렬을 하고 차례대로 끝나는 시간과 현재 사람의 시작시간과 비교를 하면 이용시간이 겹치는지 아닌지 알 수 있다.
만약에 -pq.top().first < v[i].first (컴퓨터 이용내역 중 가장 빨리 끝나는시간 < 현재 사람의 시작 시간) 이라면 pq.top()에 있는 컴퓨터는 이용이 끝난 것이므로 pq2에 push를 하여 이 컴퓨터가 빈 자리인것이라고 표시해준다.

문제 링크

boj/12764

소스코드

PS/12764.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
vector<pair<int, int>> v;
int arr[100001];
int m;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int p, q;
		cin >> p >> q;
		v.push_back({ p,q });
	}
	sort(v.begin(), v.end());
	priority_queue<pair<int, int>> pq;
	priority_queue<int,vector<int> ,greater<int>> pq2;
	pq.push({-v[0].second,0});
	arr[0]++;
	for (int i = 1; i < n; i++)
	{
		pq2.push(i);
	}
	for (int i = 1; i < v.size(); i++)
	{
	
		while (!pq.empty() && -pq.top().first < v[i].first)
		{
			pq2.push(-pq.top().second);
			pq.pop();
		}
		pq.push({ -v[i].second , -pq2.top()});
		arr[pq2.top()]++;
		pq2.pop();
		m = max(m,(int)pq.size());
		
	}
	cout << m<<'\n';
	for (int i = 0; i <m; i++)
		cout << arr[i] << ' ';
}