[백준 파이썬] 13334 철로

백준 13334

먼저 집이나 사무실을 우선 정렬한다.
끝 지점이 가장 낮은값부터 시작해 순차적으로 탐색할 수 있도록 끝 지점을 기준으로 정렬한다. 같은 지점에서 끝나는 경우 출발지점이 더 앞쪽인 기준으로 정렬한다.

# 13334 철로
import heapq

N = int(input())
h_o = [sorted(list(map(int, input().split()))) for _ in range(N)]
h_o.sort(key=lambda x: [x[1], x[0]])
D = int(input())


pq = []
max_size = 0

for i in range(N):
    start, end = h_o[i]
    # 현재 선분의 길이가 선로의 길이보다 짧다면
    if end - start <= D:
    	# 현재 선로의 끝지점에서 가장 멀리 있는 출발점부터 제거하기 위해 출발 지점을 힙에 저장
        heapq.heappush(pq, start)
    else:
        continue
	
    # 모든 출발 지점이 선로 내부에 있을 때까지
    while pq: 
    	# 가장 멀리 있는 출발 지점이
        temp = heapq.heappop(pq)
        # 선로 내에 있을 경우
        if end - temp <= D:
        	# 다시 힙에 저장하고 while문 종료
            heapq.heappush(pq, temp)
            break
    # 선로 내에 있는 선분의 수는 힙의 수와 같다 (선로는 끝지점을 기준으로 출발점과 비교했기 때문)
    max_size = max(max_size, len(pq))

print(max_size)