백준 1931번: 회의실 배정 (파이썬)

 

한 회의실을 겹치지 않게 쓸 수 있는 최대의 경우의 수를 출력하는 문제

 

제일 먼저 생각했던 건 일단 시작 시간을 기준으로 정렬

일찍 시작할수록 남는 시간이 많기 때문에 시작 시간이 제일 빠른 것부터 카운트

 

두 번째로 고민해야하는 부분은 종료 시간인데

제일 먼저 시작해놓고 제일 나중에 끝난다면 다른 사람은 회의에 참여할 수 없기 때문에

끝나는 시간이 언제인지도 파악해야 한다.

 

N = int(input())

time = list()
for i in range(N):
  # s = 회의 시작시간 , e = 회의 끝나는 시간
  s,e = map(int,input().split())
  time.append([s,e])

# 회의 시작시간을 기준으로 한 번 정렬
time.sort(key=lambda x: x[0])

# 회의 끝나는 시간을 기준으로 한 번더 정렬
time.sort(key=lambda x: x[1])

cnt = 0
end = 0
for x,y in time:
  # 회의가 끝나는 시간이 시작하는 시간보다 늦으면 안되므로
  if x >= end:
    cnt += 1
    end = y
print(cnt)

 

알고리즘 분류 : 그리디 알고리즘, 정렬

 

처음엔 시작 시간을 기준으로 한 번 정렬 후 동일하게 시작하는 회의 시간에 대해 모든 경우를 다 계산해보려 했는데

이걸 다 어떻게 저장해야 할지도 정리가 안되었다

질문 게시판의 도움을 받아서 해결했던 문제