[백준 13334번] 철로 / C++

문제

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.

출력

출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다. 

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
//도착지점 오름차순으로 정렬, 도착지점 같으면 출발지점 오름차순으로 정렬
struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second == b.second)
			return a.first > b.first;
		else
			return a.second > b.second;
	}
};

int main() {
	int n, d, x, y;
	int answer = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	//오름차순으로 정렬된 임시큐
	priority_queue<int, vector<int>, greater<int>> temp;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		if (x > y)
			swap(x, y);
		pq.push({ x, y });
	}
	cin >> d;
	
	while (!pq.empty()) {
		int start = pq.top().first;
		int end = pq.top().second;
		pq.pop();
		//출발지점과 도착지점이 철로안에 들어갈 시 출발지점 임시큐에 넣음
		if (end - start <= d)
			temp.push(start);
		while (!temp.empty()) {
			//임시큐내 모든 원소의 출발지점이 철로안에 들어가면 반복문 종료
			//오름차순으로 정렬되었기에 앞의 원소만 확인
			if (end - temp.top() <= d)
				break;
			//출발지점이 철로안에 들어가지 못할 시 임시큐에서 제거함
			else
				temp.pop();
		}
		//최대값 갱신
		answer = max(answer, int(temp.size()));
	}

	cout << answer;
}