[Python] 1931번 회의실 배정

✏️ 문제

 

문제 파악

시작하는 시간을 기준으로 회의실을 사용하게 된다면 예제1과 같은 경우 6시간을 사용하게 되어 최대 사용할 수 있는 회의의 최대 개수가 되지 않는다.

 

그럼  끝나는 시간을 기준으로 회의실을 사용하면

사용 중인 회의의 끝나는 시간이 다른 회의의 시작하는 시간과 같거나 작으면 회의실을 또 사용할 수 있게 되므로 이 조건을 기준으로 코드를 짜면 된다.

 

알고리즘

• 그리디 알고리즘
• 정렬

 

 

코드

N = int(input())
meetings = []
result = 0

for i in range(N):
  start, end = map(int, input().split())
  meetings.append((end, start))

meetings.sort()   # end 시간을 기준으로 오름차순 배열
# print(meetings) # [(4, 1), (5, 3), (6, 0), (7, 5), (8, 3), (9, 5), (10, 6), (11, 8), (12, 8), (13, 2), (14, 12)]
end_time = 0

for meeting in meetings:
  if meeting[1] >= end_time: # meeting[1] → 시작 시간
    result += 1
    end_time = meeting[0]    # meeting[0] → 끝나는 시간

print(result)