https://www.acmicpc.net/problem/11000
처음에는 이문제와 비슷하다고 생각했는데 미묘하게 다른점이 난이도를 증가시켰다.
https://www.acmicpc.net/problem/17262
강의실을 최대한 추가 안하고 최소한의 강의실을 추가하는데 목표다.
수업 시작시간 기준으로 정렬한다
지금 수업하고 있는 종료 시간 < 다음 수업 시작 시간
강의실 추가 해야됨
지금 수업하고 있는 종료 시간 >= 다음 수업 시작 시간
강의실 추가 안하고 지금 사용하고 있는 강의실 사용하면됨
강의실이 여러개 열렸을 때 다음 수업시간은 그럼 어떤 기준으로 비교를 할까?
최소한의 강의실을 사용해야 하기 때문에 그리디적으로 접근해야 할 필요가 있었음
따라서 우선순위 큐를 사용해서 배정된 수업 중 끝나는 시간이 가장 이른(Min-heap) 을 사용하면 된다
1. heap에 제일 먼저 시작하는 강의 종료 시간을 push
2. 1~n 인덱스 까지
강의 시작 시간 < heap의 루트 노드
=> heap에 강의 종료 시간 push
강의 시작 시간 >= heap의 루트 노드
=> 루트노드를 삭제하고 현재 인덱스 강의 종료시간 push
heap에 삽입하면 Min-heap 때문에 0번째 index는 무조껀 최소값을 유지한다.즉, heap[0]은 사용중인 강의실에서 가장 빨리 끝나는 값이 저장
heap[0]에 저장된 값이 가장 빨리끝나는 강의실 이기 때문에 강의가 시작하는 시간이 빠를 경우 heap[1], heap[2] ...에저장된 강의실은 이용할 수 없다.
따라서 시작 시간 < heap[0]일 경우 무조껀 새 강의실을 사용해야하므로 push해주고
시작 시간 >= heap[0] 일 경우 heap[0] 강의실을 사용할 수 있으므로 heap[0]을 삭제하고 종료 시간 push
import sys
input = sys.stdin.readline
n = int(input())
data = []
for _ in range(n):
a,b = list(map(int,input().split()))
data.append([a,b])
data.sort()
import heapq
heap = []
heapq.heappush(heap,data[0][1])
for i in range(1,n):
if heap[0] > data[i][0]:
heapq.heappush(heap,data[i][1])
else:
heapq.heappop(heap)
heapq.heappush(heap,data[i][1])
print(len(heap))
'Algorithm > Algorithm Problem' 카테고리의 다른 글
백준 15729 방탈출(그리디) (0) | 2022.06.03 |
---|---|
백준 2072 오목(구현) (0) | 2022.06.01 |
백준 13900 순서쌍의 곱의 합(구현) (0) | 2022.05.20 |
백준 11571 분수를 소수로(구현) (0) | 2022.05.20 |
백준 7662 이중 우선순위 큐(Heapq) (0) | 2022.05.12 |