from heapq import *
def solve():
result = 0; hq = []; i = -1
for c in ch:
for i in range(i+1,N):
s,e = cow[i]
if s>c:
i -= 1
break
heappush(hq,(e,s))
while hq:
e,s = heappop(hq)
if c<=e:
result += 1
break
return result
C,N = map(int,input().split())
ch = sorted(int(input()) for i in range(C))
cow = sorted([*map(int,input().split())] for i in range(N))
print(solve())
우선순위 큐를 이용해서 해결하였다.
처음엔 단순한 정렬+스택 문제라고 생각했다. 그러나 틀렸습니다를 몇 번 겪고 나서 그렇게 풀 수 있는 문제가 아니라는 사실을 알게되었다.
풀이를 설명하면,
1. 닭과 소를 정렬한다. 소는 start를 기준으로 정렬한다.
2. 가장 작은 닭부터 닭이 포함될 수 있는 범위까지의 소를 heapq에 담는다. 이때 heapq는 start가 아닌 end를 기준으로 정렬한다.
3. 현재 닭을 포함하지 않는 소는 전부 버리고, 남은 소 중 end가 가장 작은 값을 pop한 뒤 개수를 +1 한다.
4. 결과를 출력한다.
문제를 다 풀고 나서 난이도 기여내역을 보니 약 3달 전에 풀었던 보석도둑 [백준 1202번] 보석 도둑 (Python3) (tistory.com) 과 거의 유사하다는 것을 알게되었다. 당시에도 꽤 어렵게 해결했던 문제였는데, 3달만에 다시 보니 이번에도 골치를 앓게 한 문제였다.
오늘의 교훈) 이전에 풀었던 방식을 적재적소에 활용하자