[백준][1931] 회의실 배정 | 파이썬

👉 문제 분석

 

한 개의 회의실이 있다.

n개의 회의에 대해서 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작 시간과 끝나는 시간이 주어진다.

회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아야 한다.

 

👉 알고리즘 설계

끝나는 시간기준으로 오름차순 정렬

meeting = []정의

for i in range(1,n):

    if start[i] ≥ end[i]:

        numner_meeting +=1

 

👉 코드

import sys

n= int(input())
meeting = []

for _ in range(n):
    start, end = map(int,input().split())
    meeting.append((start,end))
    
#  종료시간기준으로 오름차순 정렬하고, 시작시간을 오름차순 정렬    
meeting = sorted(meeting, key = lambda x: (x[1], x[0]))

end_time = meeting[0][1]
number_meeting = 1  #  첫번째 회의는 필수적으로 선택한다. 그리고 2번째 회의부터 비교.
for i in range(1,n):   # 0번째 강의는 무조건 뽑히니까 첫번째 강의부터 비교 
    if end_time <= meeting[i][0]:  # end_time이 강의 시작 시간보다 작으면
        end_time = meeting[i][1]
        number_meeting +=1
print(number_meeting)

 

👉 시간복잡도

O(NlogN) 

 

👉 틀린 이유

접근 방식이 틀림

 

👉  틀린 부분 수정 or 다른 풀이

가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬해야 한다.

첫번째 회의는 필수적이기 때문에, number_meeting = 1 로 정해준다.

 

👉 느낀점 or 기억할정보

sort 함수와 sorted 함수의 시간복잡도는 O(NlogN)이다.

가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬해야 한다.

첫번째 조건이 무조건 포함되는지 아닌지를 구별하자.