[그리디 알고리즘] 백준 1931번 회의실 배정

[문제]

 

https://www.acmicpc.net/problem/1931

 

[생각거리]

 

- 당연히 duration 시간을 구해서 정렬하면 될 거라고 생각했는데, 이게 아둔한 생각이었다.

- 회의 시작 시간을 기준으로 정렬하고, 그 다음에 회의 종료 시간을 기준으로 정렬하는 부분이 내가 놓친 부분.

- 그리디 알고리즘의 핵심은 얼마나 단순하게 문제에 접근하느냐인 것 같다. 

 

[코드]

n = int(input())
time_table = []
count = 1

for i in range(n):
    a,b  = map(int, input().split())
    time_table.append([a,b])
    
time_table.sort(key=lambda x:x[0])
time_table.sort(key=lambda x:x[1])

end = time_table[0][1]
for i in range(1,n):
    if time_table[i][0] >= end:
        count += 1
        end = time_table[i][1]

print(count)