13334번: 철로

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

아이디어

• 각 사람들의 집과 사무실에 상관 없이 선분 상 왼쪽에 있는 곳을 튜플의 왼쪽에 둔다. (x, y) -> x <= y
• 스위핑 방식 : 사람들 case를 정렬한 후, 각 case마다 오른쪽 점을 기준으로 한 철로를 옮기면서 철로 별 case가 얼마나 있는지 계산한다.
• case 정렬
  • 철로 안에 있는지 판별을 오른쪽 점인 y를 기준으로 판별하므로, y값을 기준으로 오름차순으로 정렬한다.
  • 철로 좌표 = (start, end)
• 우선순위큐 사용 
  • 철로 안에 case가 있으면, 해당 case를 queue에 push한다.
  • 철로 안에 없는 new case 차례라면 철로를 옮겨야 한다.
  • 철로를 new case의 end값을 기준으로 설치한다고 가정
    • 이 때, 새 철로 start의 왼쪽에 x값이 있는 선분을 모두 꺼낸다.
• 각 case가 나올 때마다 현재 철로에서의 모든 case 개수를 카운팅 한다.

# https://www.acmicpc.net/problem/13334
# heapq, sweeping
import sys
import heapq

n = int(input())
loc = [0] * n
for idx in range(n) :
    h, o = map(int, sys.stdin.readline().split())
    if h <= o :
        loc[idx] = (h, o)
    else :
        loc[idx] = (o, h)

d = int(input())        
loc = sorted(loc, key=(lambda x : (x[1], x[0])))

ans = 0
cnt = 0

case = [] # 직원의 집-사무실 케이스

track_start, track_end = loc[0][1] - d, loc[0][1]
for l in loc :
    x, y = l
    if abs(y - x) > d :
        continue
    # 완전 포함일 때
    if track_start <= x and y <= track_end :
        heapq.heappush(case, x)
        cnt = len(case)
    # 일부 포함일 때
    elif track_end < y :
        # track 갱신
        track_start, track_end = y - d, y # track_end 갱신해야 함 -> 그에 따라 track_start도 갱신
        c = case[0]# init
        while case and c < track_start : # 갱신하고 track_start에 미달하는 x 가진 이전 것들 제거해야 함
            c = heapq.heappop(case)
            if track_start <= c :
                heapq.heappush(case, c)
        # 현재 것 넣기
        heapq.heappush(case, x)
        cnt = len(case)
    
    if ans < cnt :
        ans = cnt
    # print(f"cnt : {cnt}, track : ({track_start}, {track_end}), now : ({x}, {y})")

print(ans)