백준 1931 회의실 배정 (파이썬)


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




© 2020.09. by 다로

Powered by theorydb