문제

철로
수평선 상의 서로 다른 점에 있는 집과 사무실을 통근하는 N명의 사람이 있다.
길이가 d인 철로를 건설한다 할 때, 집과 사무실 모두 해당 철로에 포함 될 수 있는 사람이 가장 많은 경우 몇명인지 출력하는 문제이다.

아이디어

핵심 아이디어

1. 편의상 왼쪽에 집, 오른쪽에 오피스가 있다고 가정하고 생각한다.
2. 모든 사람의 좌표를 오피스 좌표를 기준으로 오름차순 정렬을 한다.
3. 철로의 끝을 임의의 사람의 오피스에 설치할 때, 철로의 시작점보다 집의 좌표가 더 크다면 집의 좌표를 따로 저장해둔다.
4. 새로운 철로의 끝을 임의의 다른 사람의 오피스에 설치할 때 3의 과정을 다시 진행하고, 저장해둔 집의 좌표들이 새로운 철로의 범위 밖으로 나갔을 경우 해당 집의 좌표를 없앤다.
5. 3 ~ 4 과정을 모두 반복하며, 저장해둔 집의 좌표가 가장 많았을 때를 출력한다.

풀이 아이디어

1. n번 사람의 좌표를 입력 받을 때 좀 더 작은 좌표를 pos[n][0]에, 큰 좌표를 pos[n][1]에 저장한다.
2. key=lambda x:x[1]을 키로 하여, 큰 좌표 기준으로 오름차순 정렬을 한다.
3. abs(right - left)는 집과 오피스 사이의 거리, 이 값이 d보다 크면 철로안에 들어갈 경우가 없으므로 확인하지 않는다
4. heapq모듈로 우선순위 큐를 사용한다.
5. 우선순위 큐의 맨 앞의 값(가장 작은 값)이 right - d(철로의 범위)안에 들어갈 때까지 pop한다.

풀이

import sys
import heapq
input = sys.stdin.readline

N = int(input())
pos = [[0, 0] for _ in range(N)]
for n in range(N):
    x, y = map(int, input().split())
    pos[n] = [min(x, y), max(x, y)]  # 작은 값이 왼쪽에 오게 입력
d = int(input())
pos.sort(key=lambda x: x[1])  # 오른쪽(좀더 큰 값)을 기준으로 오름차순 정렬

hq = []
ans = 0
for p in pos:
    left, right = p
    if abs(right - left) <= d:  # 집과 오피스의 거리가 d보다 작으면 체크한다.
        while hq:
            top = hq[0]
            if top >= (right - d):
                break
            # 기존의 집,오피스중 가장 left가 멀리 있는 값이 철도의 밖에 있을 경우
            heapq.heappop(hq)  # 값을 하나 뺀다.
        heapq.heappush(hq, left)
        ans = max(len(hq), ans)

print(ans)