19598(최소 회의실 개수) - 참고

최소 회의실 개수

 

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

 

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최소 회의실 개수를 출력한다.

---

처음에 풀었는데 계속 시간 초과가 났다.

import sys
input = sys.stdin.readline

N = int(input().strip())

confs =[]
for _ in range(N):
    confs.append(list(map(int,input().split())))

confs.sort()

rooms = [confs[0]]

for i in range(1,N):
    for room in rooms:
        if room[1] <= confs[i][0]:
            room[1] = confs[i][1]
            break
    else:
        rooms.append(confs[i])

print(len(rooms))

 

그래서 여러 방법을 생각하여 우선순위 큐를 활용하였지만 아직 시간 초과가 났다.

그 이유는 rooms를 계속 탐색하는 방법이였던거 같다.

그래서 찾아보니 우선 순위 큐를 활용하고 room을 전체 탐색하는 것이 아닌 pop을 통해서 우선순위가 높은 것을 확인하는 방법을 하였다. 그리고 이 우선순위는 room에서 end를 우선순위로 받았다.

그럴 경우 end가 가장 먼저 나온 것과 start를 비교하는 방법을 활용한다.

import sys
input = sys.stdin.readline
import heapq

N = int(input().strip())

confs = []
for _ in range(N):
    # confs.put(tuple(map(int,input().split())))
    heapq.heappush(confs,list(map(int,input().split())))

rooms = []

# 처음 시작을 0을 하였다.
heapq.heappush(rooms, 0)
# 처음 룸을 잡기 때문에 1로 시작
answer = 1
# N개의 회의를 탐색
for i in range(N):
    # heappop을 통해서 start가 낮은 confs를 뽑아낸다.
    conf = heapq.heappop(confs)
    # rooms의 가장 낮은 end와 해당 회의를 start를 비교
    # start가 더 늦으면 그 회의실의 현재 end를 빼낸다.
    if rooms[0] <= conf[0]:
        heapq.heappop(rooms)
    # start가 더 빠르면 새로운 회의실을 사용해야 하기때문에
    # 회의실을 늘린다
    else:
        answer += 1
    # 해당 회의를 end를 넣는다
    heapq.heappush(rooms, conf[1])

print(answer)