[백준/Python] 13334번 : 철로

문제

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

풀이

 

그림 순서:

1 3 5

2 4

 

현재 철로 범위 내에 가장 많은 (시작점, 끝점) 범위가 포함되려면 끝점을 기준으로 검사해야 한다.

 

코드

import sys, heapq

n = int(sys.stdin.readline())
office = []

for _ in range(n):
    start, end = map(int, input().split())
    if start>end:
        start, end = end, start
    heapq.heappush(office, (end, start)) # (우선순위, 값) -> 종료 시간 기준으로 최소힙 정렬

d = int(sys.stdin.readline()) # 고려할 구간의 길이

possible = [] # 현재 철로 내에 있는 사람들 저장하는 최소힙
result = 0 # 포함되는 사람의 최대 수
cnt = 0 # 현재 possible에 들어있는 회의 개수

while office:
    end1, start1 = heapq.heappop(office) # 끝지점이 가장 빠른 사람 꺼내기
    if start1>=end1-d: # 철로 안에 포함된다면
        heapq.heappush(possible, (start1, end1)) # possible 최소힙에 넣기
        cnt+=1
    while possible:
        start2, end2 = heapq.heappop(possible) # 하나 꺼내서 철로에서 벗어나는지 확인
        if start2<end1-d: # 철로에서 벗어난다면
            cnt -= 1
        else:
            heapq.heappush(possible, (start2, end2)) # 아니라면 다시 힙에 넣기
            break
        result = max(result, cnt) # 최댓값을 저장

print(result)