会議室の手配(グリンディ)


作成日: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)
  • グリディ問題の核心はソートです.
  • 会議をできるだけ多く行うためには、会議が終わる時間を比較する必要があります.したがって、tuple会議の開始時間と終了時間をリストに保存します.
  • でリストが終了した時間を基準に、昇順に並べ替えられます.
  • Pythonにおいて、Tupleの2回の再アイテムを基準として、昇順ソート+同じ値であれば、1番目のアイテムについて、昇順ソートのコードは以下の通りである.
    l.sort(key=lambda x : (x[1], x[0]))
  • 以降、繰り返しリストにより、直前の会議終了時間が繰り返しの会議開始時間よりも小さい場合、cntの形式が増加する.