[PS] 철로 / C++ (백준 13334번)

 

 

정렬과 priority queue만 적절히 사용할 줄 알면 쉽게 풀리는 문제  

1. 사람들의 집과 사무실의 위치는 바뀌어도 상관 없으므로 first 값이 작도록 설정한 뒤, second 값을 기준으로 오름차순 정렬해줌 (second 값이 같을 경우 first 값 오름차순으로)
2. 차례대로 우선순위 큐 top에 있는 사람을 기준으로 범위 안에 들어가는 지 확인
   1. O: 우선순위 큐에 i번째 사람 추가, 범위 안에 있는 사람 수가 max인 지 확인
   2. X: 범위 안에 들어갈 때까지 top에 있는 사람을 pop해줌

 

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

pair<int, int> d[1000001];
priority_queue<pair<int, int> > prique;

bool cmp(const pair<int, int> & a, const pair<int, int> & b)
{
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}

int main()
{
	int n, k, max = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a > b) {
			int c = a;
			a = b; b = c;
		}
		d[i].first = a;
		d[i].second = b;
	}
	scanf("%d", &k);
	sort(d + 1, d + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		if (d[i].first + k < d[i].second)continue;
		while (prique.size() > 0) {
			if ( - prique.top().first + k < d[i].second) {
				prique.pop();
			}
			else break;
		}
		prique.push(make_pair(-d[i].first, -d[i].second));
		if (prique.size() > max)max = prique.size();
	}
	printf("%d\n", max);
	return 0;
}