골드2 - 백준 13334 철로

백준 13334 철로

[https://www.acmicpc.net/problem/13334](https://www.acmicpc.net/problem/13334

접근방법

이 문제는 철로를 설치하는 시작점과 끝점의 범위 안에 들어가는 사람들을 세어주어 가장 사람이 많이 포함되는 범위를 구하는 문제이다.
시작점을 차례로 옮겨가며 끝점 범위 내에 포함되는 사람들을 우선순위 큐에 넣었고, 큐의 사이즈로 범위에 포함되는 사람들 수를 구해주었다. 시작점을 옮길 때, 큐에서 시작점 범위에 벗어나는 사람들을 빼주었다.

풀이

입력을 받을 때, 두 수의 크기를 비교해주어 작은 수가 앞에 저장되도록 해서 시작점과 끝점을 구분해주었다. departure에 시작점만 저장해주었고, users에 끝점과 시작점 순으로 저장해주었다.
각각 정렬을 해주어 departure에는 시작점이 빠른 사람이 앞에 오도록, users에는 끝점이 앞에 있을수록 앞에 오도록 해주었다.
priority_queue pq는 시작점을 기준으로 작은 수가 위에 오도록 선언해주었고, start 변수에는 철로를 놓고자 하는 범위의 시작점을 departure에서 꺼내 저장해주었고, 입력받은 거리를 더해 end 끝점을 저장해주었다. index로 확인 안한 users의 범위를 확인해가며 범위에 속하면 pq에 넣어주고, pq에 속한 것 중 범위를 벗어난 게 있으면 빼주어 pq의 size를 구해 answer를 갱신해주었다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<pair<int, int>> users;
vector<int> departure;

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 a, b;
		cin >> a >> b;
		if (a > b)
		{
			int temp = a;
			a = b;
			b = temp;
		}

		departure.push_back(a);
		users.push_back({ b,a });
	}
	int dis;
	cin >> dis;

	sort(users.begin(), users.end());
	sort(departure.begin(), departure.end());

	int index = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int answer = 0;

	for (int i = 0; i < departure.size(); i++)
	{
		int start = departure[i];
		int end = start + dis;

		while (!pq.empty())
		{
			if (pq.top().first >= start)
				break;
			pq.pop();
		}

		while (true)
		{
			if (index >= users.size() || end < users[index].first)
				break;

			if (start <= users[index].second)
				pq.push({ users[index].second, users[index].first });
			index++;
		}

		if (answer < pq.size())
			answer = pq.size();
	}

	cout << answer << endl;

	return 0;
}