import sys
input = sys.stdin.readline
from bisect import bisect_left
N = int(input())
wire = []
parent = {}
for i in range(N):
wire.append([*map(int,input().split())])
wire.sort()
DP = [0]
DPi = [-1]
for i in range(N):
num = wire[i][1]
if num > DP[-1]:
DP.append(num)
DPi.append(i)
parent[i] = DPi[-2]
else:
idx = bisect_left(DP,num)
DP[idx] = num
DPi[idx] = i
parent[i] = DPi[idx-1]
check = [1]*N
x = DPi[-1]
while x != -1:
check[x] = 0
x = parent[x]
print(N-len(DP)+1)
for i in range(N):
if check[i]:
print(wire[i][0])
LIS 문제이다. 가장 긴 증가하는 부분수열 5와 똑같은 알고리즘으로 풀면 된다.
약간의 차이점만 언급하면
1. wire를 A번 노드의 숫자에 따라 sort 해준다.
2. LIS를 출력하는 것이 아니라 LIS를 이루지 않는 그 외 수열을 출력한다.
의 차이점 정도가 있을 것이다.
오늘의 교훈) LIS를 적재적소에 잘 활용하자