백준 13334 철로(python)

문제

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

13334번: 철로

---

우선순위 큐를 활용하여 스위핑 방식으로 접근하였습니다. 집과 사무실 위치를 위치에 맞게 리스트에 저장해 준 다음 오른쪽을 기준으로 오름차순 정렬해주었습니다. 그 뒤 리스트에 주어진 값들을 차례로 순회하면서 주어진 철로 길이 안에 해당되면 큐에 넣어 주었습니다. 큐 최소 힙을 만들며 왼쪽 좌표만을 넣어 주었습니다. 큐에 있는 값들과 순회하면서 만난 새로운 값들을 비교해주면서 새로운 값의 오른쪽 좌표와 큐의 맨 앞에 있는 값(가장 왼편에 있는 좌표)의 거리가 철로 길이에 포함될 수 없다면  그 값을 빼주고 포함되어질 수 있다면 큐 안의 값 확인을 멈추고 최댓값을 갱신해 줍니다.

---

소스코드 

import sys
import heapq
input = sys.stdin.readline

N = int(input().rstrip())
arr = []
heap = []
maxi = 0
for i in range(N):
    h, o = map(int, input().rstrip().split())
    if h > o:
        arr.append([o, h])
    else:
        arr.append([h, o])


d = int(input())
arr.sort(key=lambda x: (x[1], x[0]))


for i in range(len(arr)):
    rp = arr[i][1]
    lp = arr[i][0]

    if rp-lp <= d:
        heapq.heappush(heap, lp)

    else:
        continue

    while len(heap) != 0:
        tmp = heap[0]
        if rp-tmp <= d:
            break
        else:
            heapq.heappop(heap)

    maxi = max(maxi, len(heap))


print(maxi)