김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
출력
강의실의 개수를 출력하라.
과정
최소힙을 이용하여 풀어준다.
시작 시간 순서로 정렬한 후 heap에 첫 시간의 끝나는 시간을 넣어주고
다음 시간의 시작 시간과 비교하며 push pop 해준다.
예제 입력
3
1 3
2 4
3 5
예제 출력
2
풀이
import heapq
import sys
input = sys.stdin.readline
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort()
heap = []
heapq.heappush(heap, lst[0][1])
for i in range(1, n):
if len(heap) != 0 and lst[i][0] >= heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, lst[i][1])
print(len(heap))
한 줄씩 해석해보기
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort()
시작 시간과 끝나는 시간을 입력받은 후 정렬한다.
heap = []
heapq.heappush(heap, lst[0][1])
for i in range(1, n):
if len(heap) != 0 and lst[i][0] >= heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, lst[i][1])
print(len(heap))
heap을 사용해 리스트의 첫번째값의 끝나는 시간을 넣어준다.
그 후 리스트의 i번째 시작 시간이 heap의 첫번째 값보다 크거나 같다면 heappop을 통해 제거한다.
