[BOJ][python] 1913_회의실배정

문제 이름 : 1931번: 회의실 배정

풀이 :

• key point : 그리디를 이용해서 해결 할 수 있다는 것을 알아차리자.
  최대한 많은 회의를 배정할 수 있는 요인을 생각해보자

• Logic:

  1. 위의 풀이에 따라 시작 시간 기준으로 회의를 정렬한 후 종료 시간 기준으로도 한번 더 회의를 정렬시킨다.
     meetings.sort(key=lambda x: x[0])
     meetings.sort( key = lambda x:x[1])
  2. 정렬한 회의를 꼬리잡기 식으로 풀어준다. 이전 회의의 끝 시간보다 회의의 시작 시간이 빠를 경우, 해당 회의는 생략한다.
     end = meetings[0][1]
     count = 1
     for i in range(1,len(meetings)):
     if meetings[i][0]<end:
     continue
     end= meetings[i][1]
     count += 1

import sys
input= sys.stdin.readline

N = int(input()) # 회의 총 갯수 
meetings=[]
schedule=[]

for _ in range(N):  # 각각의 회의 시작, 끝 
    a,b = map(int, input().split())
    meetings.append((a,b))

meetings.sort(key=lambda x: x[0])
meetings.sort( key = lambda x:x[1])

end = meetings[0][1]
count = 1
for i in range(1,len(meetings)):
    if meetings[i][0]<end:
        continue
    end= meetings[i][1]
    count += 1

print(count)

전체적으로 느낀점 :

왜 그리디인지 이해가 안 갔는데 다른 사람의 풀이 과정을 보고 그리디를 적용시키는 방법을 깨달았다.
그리는 당장의 상황에서 최고의 선택을 하는 것이다.
회의실을 사용하고 있다고 가정할때, 해당 회의가 끝난 후에 가장 많은 회의가 뒤에 있기 위해서는 회의가 최대한 빨리 끝나야 한다. 즉 회의의 종료시간은 빠르면 빠를 수록 좋다. ( 나는 이 조건만으로 풀이를 할려고 시도했는데 시간 초과로 실패했다.)
만약 회의의 종료시간이 같다면 시작 시간이 빠를 수록 좋다. 예를 들어서 (9,10)과 (10,10)이 있다면, (10,10)을 선택하게되면
(9,10)의 회의는 못하게 된다. 하지만 (9,10)부터 하면 (9,10) (10,10) 이 가능하다.