13334 철로

문제

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

13334번: 철로

 

접근

• 가장 처음 시도한 방법은 정렬과 스위핑을 사용해서 철도의 구간과 구간에 들어가는 경로의 개수를 갱신해나가는 방법으로 풀이했으나 틀림 -> 반례가 무엇인지 못찾겠다...
• 다른 방법으로 정렬된 전체 경로들(시작점과 끝점이 철도의 길이 d보다 작거나 같은 경로들)에 대해, 철도의 길이 d에 함께 포함될 수 있는 경로들을 따로 저장(q)해놓고, 그 구간을 벗어나는 경로를 만날때마다 새로운 경로에 맞춰 q에 저장한 경로 정보를 갱신하기로 결정
• 갱신할 때마다 경로의 값이 작은 경로들 순으로 비교해야 하므로 우선순위큐를 사용했으나 틀림
• 반례를 통해 전체 경로를 정렬할 때 시작점이 아닌 끝점을 기준으로 정렬해야 함을 깨닫고 수정 후 풀수 있었다.

 

풀이

• 우선 경로의 길이가 철도의 길이인 d보다 큰 경로들은 빼고 풀이한다.
• 각 (기준) 경로에 대해 우선순위큐 안에 있는 원소들 중 기준 경로와 같은 철도 구간에 포함될 수 있는지 확인 후, 불가능하다면 제거한다.
• 우선순위큐 안에 같이 포함된 원소는 같은 철도 구간에 포함될 수 있다는 뜻이므로, 매 시행마다 ans를 우선순위큐의 길이의 최대값으로 갱신한다.

import heapq

n = int(input())
a = []
for _ in range(n):
    s, e = map(int, input().split())
    if s > e:
        s, e = e, s
    a.append((s, e))

d = int(input())
b = [(s, e) for s, e in a if e - s <= d]
b.sort(key=lambda x:x[1])

ans = 0
q = []
for s, e in b:
    if not q:
        heapq.heappush(q, (s, e))
    else:
        while q and e - q[0][0] > d:
            heapq.heappop(q)
        heapq.heappush(q, (s, e))

    ans = max(ans, len(q))
print(ans)