문제
접근
그리디 알고리즘으로 해결할 수 있다.
회의 시간표를 끝나는 시간 기준으로 정렬한다.
끝나는 시간이 빠른 순서대로 회의를 잡아주면 항상 최적해이다.
특정 회의가 끝났을 때 시간을 기준으로 해당 시간보다 늦게 시작하는 회의들 중에서 가장 빨리 끝나는 회의를 진행한다.
이를 반복하면 항상 최대한 많은 회의를 진행할 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
arr = sorted(arr, key = lambda x:(x[1], x[0]))
ans = 0
nowEnd = -1
for start, end in arr:
if start >= nowEnd:
nowEnd = end
ans += 1
print(ans)