초기 접근
우선순위 큐 예상은 했으나
각각의 범위가 Xn-Yn 일때
가장 긴 스케쥴을 잡는 방법인, Yn의 최저에 가장 많이 붙히는 식으로 생각함
ㄴ> 다른 알고리즘임
초기 접근으로하면 한개의 스케쥴에 대해 DFS처럼 접근하게 되므로 아무리 줄이려고 해도 연산은
O(N^2)에 비례하므로 풀 수 없다.
최대힙/최소힙 등 힙을 2개를 써야하는 것을 예상은 했지만
둘다 담아놓은 상태에서 서로다른 조건의 큐를 처리를 하려고 하니 큐에
남아있는 나머지 값에 중복도 있고 조건도 중복되어 연산도 실패하고 알고리즘도 실패한다.
ㄴ>그냥 기준이 되는 Y최소힙을 비워넣기만 했으면 됐는데, 이 쉬운 생각을 왜 못했을까...
Yn이 짧은 걸 붙히는것 보다, 큐를 2개 만들고 Yn이 가장 짧은 것을 기준으로해서 그것보다 더 큰게 있으면 붙힌다
Yn중 짧은 순으로 살피고 그것보다 Yn < Xk인 k가 있는지 x에 대한 최소힙을 가지고서 판단
조건을 충족하지 않으면 그냥 그대로 y에 대한 최소힙으로 삽입
삽입해도 매번 y최소에서 기준을 뽑아서 쓰니 가장 작은 것만을 따지게 된다.
즉 매번 붙힐 수 있는게 존재하면 바로 붙힌다.
챌린징 포인트
yminq xminq둘다 값을 넣어둔 상태에서 자꾸 고려하다보니
쓰레기값을 담을 새로운 큐를 생각하였고 그것을 가지고 문제를 해결하려고 너무 복잡하게 생각하였음
ㄴ> yminq에는 빈값으로 두고 한 번씩 탐색하면서 흝으면 O(N)에 해결할 수 있다.
*미리 값을 담아두고 생각하면 복잡해진다.
기준이 될 큐는 처음부터 빈공간으로 시작해서 담는 과정에 대한 알고리즘을 구현하면 해결할 수 있다.
구현
import sys
import heapq
n = int(input())
xminq = []
for _ in range(n):
x, y = map(int,sys.stdin.readline().strip().split())
heapq.heappush(xminq, (x,y)) #정렬기준 [0]에 [1]에는 값을
###정렬 잘 되는지부터 확인하기 #y기준으로도 정렬이 잘되었는지 확인
yminq = []
while(xminq):
if yminq:
stand = heapq.heappop(yminq)
temp = heapq.heappop(xminq)
if (stand[1][1] > temp[0]):#index 다시 살피기
heapq.heappush(yminq, stand)
heapq.heappush(yminq, (temp[1],temp))
else:
heapq.heappush(yminq, (temp[1],(stand[1][0],temp[1])))
else:
temp = heapq.heappop(xminq)
heapq.heappush(yminq, (temp[1],temp))
print(len(yminq))