방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 N 이 200,000 이므로 이중 for문으로는 해결하지 못한다는 것을 알 수 있습니다. 40,000,000,000 이므로.

따라서 종료시점 중 가작 작은 값을 꺼내려면 최소힙을 사용해야 함을 알 수 있습니다. 만약 sort를 사용해서 매번 오름차순으로 한다면 

N * NlogN이므로 2 * 10^13 정도로 이 역시 시간초과가 난다는 것을 알 수 있습니다.

소스코드

import heapq

n = int(input())
arr = []
q = []
ans = 0
for _ in range(n):
  a, b = map(int, input().split())
  arr.append((a, b))

arr.sort(key = lambda x: (x[0], [1]))
heapq.heappush(q, arr[0][1])
ans += 1

for i in range(1, n):
  a, b = arr[i]
  if q[0] > a:
    heapq.heappush(q, b)
    ans += 1
  else:
    heapq.heappop(q)
    heapq.heappush(q, b)
print(ans)