[백준/BOJ] 11666. 워크스테이션 배정 [Gold 3]

11666. 워크스테이션 배정

문제출처 : https://www.acmicpc.net/problem/11666

code

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

int main()
{
	int n, m, lock = 0;
	cin >> n >> m;
	vector<pair<int, int>>v(n);
	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++)
	{
		if (pq.empty())
		{
			pq.push(-(v[i].first + v[i].second));
			continue;
		}
		if (v[i].first < -pq.top())
		{
			pq.push(-(v[i].first + v[i].second));
			continue;
		}
		if (v[i].first <= -pq.top() + m)
		{
			lock++;
			pq.pop();
			pq.push(-(v[i].first + v[i].second));
		}
		else
		{
			pq.pop();
			i--;
		}
	}

	cout << lock;

	return 0;
}

이런 유형의 문제를 풀때 선분을 하나 그어서 범위를 표시해가면서 풀면 쉽게 풀리는것 같다.
그렇게 어려운 문제는 아니였는데 마지막 else문에서 pop만하면 되는데 멍청하게 push도 같이 넣었다가 시간이 좀걸렸다.

priority_queue로 워크스테이션 사용여부를 구현하는것이 포인트다.