[백준/파이썬] 1931번 회의실 배정 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1931번 회의실 배정
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

각 회의의 시작/종료 시간이 주어질 때, 서로 겹치지 않게 배정할 수 있는 회의의 최대 개수를 구하는 문제입니다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

import sys;read=sys.stdin.readline
c=s=0
for i in sorted([list(map(int,read().split()))for _ in range(int(read()))],key=lambda x:(x[1],x[0])):
    if s<=i[0]:
        s=i[1]
        c+=1
print(c)

설명

그리디의 기준은 끝나는 시간이 가장 이른 회의부터 선택하는 것입니다.

• 회의를 (종료 시간, 시작 시간) 기준으로 정렬
• 현재 선택된 마지막 회의 종료 시각 s보다 시작 시각이 크거나 같으면 채택
• 채택할 때마다 s를 해당 회의 종료 시각으로 갱신

종료 시간이 빠른 회의를 먼저 고르는 전략이 뒤에 더 많은 회의를 넣을 수 있는 여지를 최대화하므로 최적해를 보장합니다.

---

• 백준 문제풀이 전체 목록 보기

---