회의실 배정(그리디)

생성일: 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를 늘려가는 형식이다.