1931. 회의실 배정

분명 문제가 그리디 카테고리에 있었지만 처음엔 완전탐색으로 풀었던 것 같다.

0부터 시작해 가능한 경우를 다 세보면서, 최대 회의 수를 max로 두고 마지막 max를 출력하는 방식으로 풀었다.

그렇게 하니 예시에 대한 답은 맞췄지만 채점 중 시간초과가 나왔다.

 

결국 구글링으로 힌트를 찾았다.

포인트는 회의가 끝나는 시간을 기준으로 정렬한 후에 그리디로 푸는 것.

회의가 끝나는 시간을 기준으로 삼으면, 앞으로 회의를 진행할 수 있는 남은 시간이 많이 남기 때문이라는 것이다.

 

만약 이 문제 유형이 그리디라는 것을 몰랐다면, 그리디로 풀어낼 수 있었을까?

 

생각하지 못했을 것 같다.

아직 처음이니까, 풀다보면 감이 오겠지.

 

answer = 0

n = int(input())
timeTable = []
for i in range(n):
    timeTable.append(tuple(map(int, input().split())))
timeTable.sort(key=lambda t: (t[1], t[0]))

last = 0
for t in timeTable:
    if t[0] >= last:
        answer += 1
        last = t[1]

print(answer)