[BOJ] 13334 철도

https://www.acmicpc.net/problem/13334

라인스위핑 문제이다. 집과 사무실 좌표로 구성된 선분들 주어지고, 길이가 d인 철도를 설치할 때 가능한 많은 선분을 포함하게 하는 문제이다.

기존 스위핑 문제에서는 길이가 가변적이었는데, 이번에는 고정된 길이를 주고 포함여부를 확인하라고 해서 어렵게 느껴졌다.

게다가 이전 문제들에서 사용했던 템플릿이 적용되지 않기도 해서 도움을 받아서 해결했다.

해결방법의 요지는 각 선분의 끝지점을 기준으로 정렬하고 끝에서부터 철도를 거꾸로 설치해간다.
각 선분의 끝지점별로 철도가 설치되면 철도의 시작점에 따라서 넘어가는 선분들이 생기는데 이거는 우선순위 큐로 제거해준다.
이런식으로 해결했는데 아직 정확히 이해가 가지않고 언제 이런 방법을 써야하고 언제 이전에 사용했던 것을 써야할 지 잘 모르겠어서 비슷한 문제를 더 풀어봐야겠다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

n = int(input())

loc = []

for _ in range(n):
  a, b = map(int,input().split())
  
  loc.append((min(a, b), max(a, b)))

loc.sort(key=lambda x: (x[1], x[0]))

d = int(input())

heap = []
count = 0

for l in loc:
  h, o = l
  heappush(heap, h)
  start = o - d
  end = o
  
  while heap and heap[0] < start:
    heappop(heap)
  count = max(count, len(heap))
  
print(count)