[백준][Python] 10165 버스노선

라인 스위핑. 어떤 기준을 정하고 탈락은 어떻게 시킬 것이냐?

기준이 확장되어야한다면 넓은 범위를 먼저 조사해 기준으로 잡고

기준이 작아져야한다면 좁은 범위를 먼저 조사해 기준으로 잡아야 한다.

 

import sys
input = sys.stdin.readline


N = int(input())
M = int(input())
path1 = []
path2 = []
visited = {i: False for i in range(1,M+1)}
minA = int(1e12)
maxB = -1
# 0을 거치는 최장 범위 minA ~ maxB를 구하고 모든 간선을 0을 거치는 것과 그렇지 않은것으로 나눔.
for i in range(1,M+1):
    a, b = map(int, input().split())

    if a <= b:
        path1.append((a,b,i))
    else:
        minA = min(minA, a)
        maxB = max(maxB, b)
        b = b + N
        path2.append((a,b,i))
    visited[i] = True
# 모든 간선을 시작점 오름차순, 종료지점 내림차순으로 정리.(종료지점이 길어야 뒤에애들은 다 탈락.)
path1.sort(key=lambda x : (x[0],-x[1]))
path2.sort(key=lambda x : (x[0],-x[1]))

right = 0
for i in range(len(path1)):
    # 0을 거치지 않는 노선의 시작점과 종료점이 영역 안으로 들어온 path면 삭제시킴.(라인 스위핑)
    if minA <= path1[i][0]:
        visited[path1[i][2]] = False
    if maxB >= path1[i][1]:
        visited[path1[i][2]] = False
    # 마찬가지로 right 안쪽이면 다 삭제.
    if path1[i][1] <= right:
        visited[path1[i][2]] = False
    # 포함 안됐으면 간선 추가시킴.
    else:
        right = path1[i][1]

# 0거쳐가는애들도 오른쪽 끝이랑 0이랑 비교해서 점점 범위 늘려나감(시작점, 끝점.)
right = 0
for i in range(len(path2)):
    if path2[i][1] <= right:
        visited[path2[i][2]] = False
    else:
        right = path2[i][1]
    
for i in range(1,M+1):
    if visited[i]:
        print(i,end=' ')