13334. 철로

h,o의 범위가 매우 크기 때문에 완전 탐색은 배제한다. 이 문제는 heap 자료구조를 사용한다. 입력을 받을 때 주의할 점은 정렬되어서 입력을 주지 않아서 sorted로 정렬 시켜줘야한다.

 

그 후에, 끝 위치 기준으로 정렬을 해준다. -> 끝 위치에서 d만큼 앞으로 가서 포함되는것 체크 할 것이므로 가장 가까운 끝 부터 찾는다.

정렬된 구간에서 d만큼 거슬러 올라간 부분을 lim으로 두고, lim보다 start가 이상이면 힙에 넣어준다. 즉 포함되는 구간이다. 그리고 마지막 조건으로 힙이 존재하고 힙의 첫번째 원소가 lim보다 작다면 구간에 포함되지 않으므로 모두 빼준다.

 

힙을 생각하는 과정이 어려운 문제 같다. 하지만 비슷한 느낌의 문제를 풀어본적이 있어서 생각해 낼 수 있었다.

 

import sys,heapq
input = sys.stdin.readline
n = int(input())
gugan = [sorted(list(map(int, input().split()))) for _ in range(n)]
d = int(input())

gugan.sort(key= lambda x: x[1])
# print(gugan)

ans = -1 
heap =[]
for s,e in gugan:
  lim = e - d
  if s >= lim:
    heapq.heappush(heap, s)
  while heap and heap[0] < lim:
    heapq.heappop(heap)
  ans = max(ans, len(heap))
print(ans)