회의실 배정(그리디)
생성일: 2022년 1월 18일 오후 5:32
구현 코드
# 회의실 배정(그리디)
import sys
sys.stdin = open("in1.txt", "rt")
n = int(input())
l = []
for _ in range(n):
a, b = map(int, input().split())
l.append((a,b))
# 튜플이 들어 있는 list를 튜플의 두번째 아이템을 기준으로 정렬하는 방법(람다 사용)
l.sort(key=lambda x : (x[1], x[0]))
et = 0
cnt = 0
for s, e in l:
if s >= et:
et = e
cnt += 1
print(cnt)
- 그리디 문제의 핵심은 정렬이다.
- 회의가 최대한 많이 진행되도록 하기 위해 비교해야할 것은 회의가 끝나는 시간이다. 따라서 튜플로 회의 시작 시간과 끝 시간을 담고 리스트에 저장한다.
- 해당 리스트를 끝나는 시간을 기준으로 오름차순으로 정렬한다.
- 파이썬에서 튜플의 두번재 아이템을 기준으로 오름차순 정렬 + 같은 값이라면 첫번째 아이템을 기준으로 오름차순으로 정렬하는 코드는 다음과 같다.
l.sort(key=lambda x : (x[1], x[0]))
- 그 후에는 리스트를 반복문을 통해 돌면서 이전 회의가 끝나는 시간이 반복문에 들어온 회의의 시작 시간보다 작다면 cnt를 늘려가는 형식이다.
Author And Source
이 문제에 관하여(회의실 배정(그리디)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/회의실-배정그리디저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)