[python/백준] 11000번 : 강의실 배정

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

11000번: 강의실 배정

 

⭐ 문제

 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

 

 

 

 

⭐ 코드분석

 

1. 힙자료구조

import heapq

 

 

2. 반복하는 횟수 받기

n = int(input())

 

 

3.  강의가 시작시간, 끝나는 시간 입력 받기

lecture_list = [list(map(int, input().split())) for _ in range(n)]

 

 

4. 작은 순으로 정렬하기

lecture_list.sort()

 

 

5. 첫번째 강의 끝나는 시간 우선순위 큐에 정렬

lecture_queue = []

heapq.heappush(lecture_queue, lecture_list[0][1])

 

 

6. 강의 리스트에서 1번째 인덱스 부터 마지막 반복문 실행

for i in range(1, n):

 

7. 만약 강의의 시작 시간이 우선순위 큐의 첫번째 인덱스 보다 작으면 끝나는 시간을 우선순위 큐에 추가 

      if lecture_list[i][0] < lecture_queue[0]:

            heapq.heappush(lecture_queue, lecture_list[i][1])

 

 

8. 아니면 우선순위 큐의 첫번째 인덱스를 빼낸후 해당 강의의 끝나는 시간을 우선순위 큐에 추가함

     else:

            heapq.heappop(lecture_queue)

            heapq.heappush(lecture_queue, lecture_list[i][1])

 

9. 필요한 강의실 갯수 출력

print(len(lecture_queue))

 

 

 

 

 

 

 

 

 

 

⭐ 코드

 

import heapq

n = int(input())

lecture_list = [list(map(int, input().split())) for _ in range(n)]

lecture_list.sort()

lecture_queue = []
heapq.heappush(lecture_queue, lecture_list[0][1])

for i in range(1, n):
    if lecture_list[i][0] < lecture_queue[0]:
        heapq.heappush(lecture_queue, lecture_list[i][1])
    else:
        heapq.heappop(lecture_queue)
        heapq.heappush(lecture_queue, lecture_list[i][1])

print(len(lecture_queue))