문제

입력 , 출력

solution

import sys
import heapq


heap = []
input = sys.stdin.readline
n = int(input())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])
arr.sort(key=lambda x: x[0])
heapq.heappush(heap, arr[0][1])  #첫번째 강의가 끝나는 시간을 넣음
for i in range(1, n):
    if heap[0] > arr[i][0]:
        heapq.heappush(heap, arr[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, arr[i][1])
print(len(heap))

설명

파이썬 sort()함수

sort함수에는 매개변수로 key를 받을 수 있는데
arr.sort(key=lambda a:a[0])
이런식으로 하면 각 배열에서 0번째를 기준으로 정렬을 할 수 있다.
[(1,2,3),(2,3,4)] 이런배열이 있으면 0번째 인덱스 기준으로 정렬이 된다.

파이썬 heapq

heapq로 list배열을 힙처럼 사용할 수 있게 해준다.
heapq.heappush , heapq.heappop
이 두개의 시간복잡도는 logn만큼 걸린다.

여기서 시간복잡도는 n(입력) + nlogn(퀵소트) + nlogn(heappush,heappop을 실행하는 시간) 만큼 걸린다.

처음에는 강의실을 이용하는 시간을 key값으로 잡아서 정렬을 해준다.

heap에 젤 먼저 시작하는 강의종료시간을 push한다.
그리고 1번 인덱스부터 ~ n번 인덱스까지
현재 인덱스 강의 시작시간이 heap에서 루트노드 보다 작을경우
heap에 강의 종료시간을 push를 한다.
강의 시작 시간이 heap 루트노드보다 크거나 같을경우에는
루트노드를 삭제하고 현재인덱스 강의 종료시간을 push해준다.

heap에 삽입을 하면 최소힙을 유지를 하므로
heap에서 0 번째 인덱스는 무조건 가장 작은값을 유지한다.
즉 heap[0]에는 사용중인 강의실에서 가장 빨리 끝나는 값이 저장되어있다.
heap[0] 에 저장된 값이 가장빨리 끝나는 강의실 이므로 강의가 시작하는 시간이 빠를경우에는
heap[1],heap[2].. 에 저장된 강의실을 이용할 수 없다.
그러니 시작시간 < heap[0]일 경우에는 무조건 새 강의실을 사용해야하므로 heappush를 해준다.
heap[0]보다 강의시작시간이 클경우에는 heap[0]강의실을 사용할 수 있으므로 heap[0]을 삭제해주고 해당 강의 종료시간을 넣어주면 된다.

이렇게 반복한 뒤에 heap에 저장된 길이가 사용해야하는 강의실 개수이므로
출력하면 정답이다.

후기

어렵다