<정렬> 11000번 강의실 배정 with 파이썬

 

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

 

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

 

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

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

정답비율

28.936%

 

import sys
import heapq
input = sys.stdin.readline
lst = []
rooms = []

n = int(input())
for _ in range(n):
    x, y = map(int, input().split())
    lst.append((x, y))
lst.sort()
heapq.heappush(rooms, lst[0][1])

for i in range(1, n):
    x, y = lst[i][0], lst[i][1]
    if rooms[0] <= x:
        heapq.heappop(rooms)
        heapq.heappush(rooms, y)
    else :
        heapq.heappush(rooms, y)
print(len(rooms))

 

 - 정렬알고리즘을 풀기위해서 고른 문제였는데 정렬보다는 우선순위 큐나 그리디에 가까운 것 같다.

 

 - 우선순위 큐를 쓰면 편할 것 같아서 처음부터 사용했으나 시간초과를 생각하지 못하고 이중 for문을 썼다가 오답처리를 받았다.

 

 - 조금 생각해보니 rooms에는 각 강의실별 가장 마지막의 마지막 시간만 담으면 되는 거였다.

 

 - 우선 입력받은 튜플을 정렬시킨다. 그렇게 되면 시간이 빠른 순으로 정렬이 될 것이다.

 

 - 우선 순위 큐인 rooms에 리스트의 첫번 째 값의 마치는 시간을 넣는다.

 

 - for 문으로 lst의 두 번째(1) 튜플부터 비교를 시작한다.

 

 - 만약 현재 rooms에서 가장 작은값(강의실 별 마치는 시간중 가장 빠른 강의실의 마치는 시간)보다 시작하는 시간이 크면 rooms에서 그 값을 빼고 새로운 도착 시간을 넣어준다.

 

 - 그렇지 않다면 새로운 강의실을 할당받아야 하므로 rooms에 새로운 도착시간을 넣는다.

 

 - rooms의 길이를 출력한다.

 

 - 테스트 케이스를 다음과 같이 돌려 rooms를 확인해 볼 수 있다.

 

5
1 3
3 5
2 4
4 7
2 5

[5, 5, 7]

 

---

 

 

참고

 

11000번: 강의실 배정