99클럽 코테 스터디 19일차 TIL - 그리디 (백준1374 - 강의실)

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

• 오늘의 학습 키워드 : 그리디
• 문제 설명

시작한 시간으로 정렬 [3, 2, 14], [1, 3, 8], [8, 6, 27], [5, 6, 20], [2, 7, 13], [4, 12, 18], [6, 15, 21], [7, 20, 25]

강의실 1	2 ~ 14	20 ~ 25
강의실 2	3 ~ 8	12 ~ 18
강의실 3	6 ~ 27
강의실 4	6~20
강의실 5	7 ~ 13	15 ~ 21

1. 정렬 : 강의의 시작 시간을 기준으로 오름차순 정렬
2. 우선순위 큐(힙) 활용: 각 강의실의 가장 빠른 종료 시간을 추적

3-1. 강의 시작 시간 ≥ 가장 빠른 종료 시간	기존 강의실 재사용 (heappop) -> 강의 종료 시간 추가(heappush)	새 강의가 이전 강의 이후에 시작 가능
3-2. 강의 시작 시간 < 가장 빠른 종료 시간	새 강의실 추가 (heappush)	새 강의가 기존 강의실에서 시작 불가

• 공부한 내용 
  

  import sys
  import heapq
  
  N= int(sys.stdin.readline().strip())
  classes = [tuple(map(int, input().split())) for _ in range(N)]
  
  # 2. 강의 시작 시간 기준 정렬
  classes.sort(key=lambda x: x[1])
  
  # 3. 최소 힙 생성
  heap = [classes[0][2]]
  
  # 4. 강의실 배정
  for _, start, end in classes[1:]:
      if heap[0] <= start:  # 기존 강의실 사용 가능
          heapq.heappop(heap)
      heapq.heappush(heap, end)
  
  # 5. 최소 강의실 수 출력
  print(len(heap))

• 오늘의 회고
  • 오늘은 이해가 되지만 먼가 풀이가 그렇게 바로 떠오르지 않아서 좀 고민했던 시간이였달까?
  • 정렬을 해서 사용하고 먼가 문제는 이해되는데 이걸 어찌 풀어야 잘 풀었다고 소문날까~ 이런느낌으로 고민하는 시간이었다.