[백준] 1931번 : 회의실배정(탐욕 알고리즘)- 파이썬[Python]

문제

1931번: 회의실 배정

풀이

import sys
N=int(sys.stdin.readline())
N_list=[] #회의실 시간 리스트
S_list=[] #가능한 회의 추가하는 리스트
for i in range(N):
  N_list.append(list(map(int,sys.stdin.readline().split())))
N_list=sorted(N_list, key= lambda x: (x[1],x[0],x[1]-x[0])) 
#끝나는 시간, 시작 시간, 걸리는 시간 순으로 정렬 
for i in range(len(N_list)):
  if len(S_list)==0: #첫 회의일 경우
    S_list.append(N_list[i])
  elif S_list[-1][1]<=N_list[i][0]: #끝나는 시간 이후 회의일 경우 추가
    S_list.append(N_list[i])


print(len(S_list))

정렬이 중요한 문제

탐욕 알고리즘은 매 순간마다 최선의 선택을 하는 알고리즘이기 때문에

매 순간이 최선이 되게끔 정렬을 하는 것이 중요하다.

처음에는 끝나는 시간과 걸리는 시간 순으로만 정렬을 했었는데

(1 1)(2 2)(1 2)와 같이 회의가 시작하자마자 끝나는 회의가 선 순위로 정렬이 되어 인식을 못하는 경우가 생겨서

시작하는 시간도 정렬 기준에 포함하여 문제를 해결했다.