1import heapq
2
3N = int(input())
4
5L = []
6for _ in range(N):
7 L.append(tuple(map(int, input().split())))
8
9L.sort()
10q = []
11
12heapq.heappush(q, L[0][1])
13for i in L[1:]:
14 if q[0] > i[0]:
15 heapq.heappush(q, i[1])
16 else:
17 heapq.heappop(q)
18 heapq.heappush(q, i[1])
19
20print (len(q))
문제
- 강의 개수와 강의 당 시작시간, 종료시간이 주어진다
- 필요한 강의실 개수를 구하라 (연강 가능))
-
TC
- input
3 1 3 2 4 3 5
- output
4
- input
해결 방법
-
- 강의 시간 리스트를 시작 시간에 따라 정렬한다
-
- 순회하면서 최소힙에서 가장 높은 우선순위와 현재 강의의 시작 시간을 비교한다
- 최소힙이 크면 그냥 추가
- 최소힙이 작거나 같으면 교체한다 (두 강의는 이어졌다)
-
- 힙의 원소 개수를 출력한다