[백준] 11000번 파이썬 _ 강의실 배정

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

11000번: 강의실 배정

 

문제유형 : 정렬, 그리디, 우선순위큐

 

문제풀이 :

 

• 이전 회의의 종료시간과 현재 회의의 시작시간을 비교한다.
  • 이때 서로 같은 강의실 이용이 가능하다면 큐의 원소를 다음회의로 갱신하도록 하고
  • 서로 다른 강의실을 이용해야한다면 큐에 해당강의의 종료시간을 추가한다.
• 회의실 배정 문제와 비슷하다. 회의실배정문제에서는 연속된 회의를 가장많이 찾기만 하면 되는거였고 조건에 만족하지 않는애들은 버리면 되었는데, 여기서는 그런 애들도 다 체크해줘야되기때문에 큐를 이용해야한다.

 

• 또한 n이 2만이므로 n제곱의 시간복잡도로는 시간초과가난다. 아래코드는 전체시간을 한번 도는데 n, 속할수있는 강의실을 찾는과정 logn(우선순위큐) 총 O(nlogn)의 시간복잡도를 갖는다. 

 

 

정답코드 :

import sys
import heapq
input = sys.stdin.readline

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

# 시작시간을 기준으로 소팅
time = sorted(time, key=lambda x:x[0])

q = []
first= time.pop(0)
heapq.heappush(q, first[1])

for i in time:
    #print(i)
    if q[0] <= i[0]:
        heapq.heappop(q)
        heapq.heappush(q, i[1])
    else:
        heapq.heappush(q, i[1])

print(len(q))