백준 1931 회의실 배정 (파이썬)
접근방식
- 그리디 알고리즘 문제 중 기본인 활동 선택 문제이다.
- 핵심은 회의의 시작시간과 끝나는 시간이 같을 수 있으므로 시작시간, 끝나는 시간을 기준으로 두번 정렬을 해주어야한다는 것이다.
- 정렬 후에는 다음에 올 시작시간이 현재 종료 시간 후인 것을 찾고 카운트를 하나씩 늘려나가면 된다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
arr = []
for _ in range(n):
arr.append(list(map(int, sys.stdin.readline().split())))
arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:x[1])
c = 0
e = 0
for i,j in arr:
if i >= e:
e = j
c = c + 1
print(c)
참고
https://pacific-ocean.tistory.com/236