会議室の手配(グリンディ)
4316 ワード
作成日:2022年1月18日午後5:32
グリディ問題の核心はソートです. 会議をできるだけ多く行うためには、会議が終わる時間を比較する必要があります.したがって、tuple会議の開始時間と終了時間をリストに保存します. でリストが終了した時間を基準に、昇順に並べ替えられます. Pythonにおいて、Tupleの2回の再アイテムを基準として、昇順ソート+同じ値であれば、1番目のアイテムについて、昇順ソートのコードは以下の通りである. 以降、繰り返しリストにより、直前の会議終了時間が繰り返しの会議開始時間よりも小さい場合、cntの形式が増加する.
インプリメンテーションコード
# 회의실 배정(그리디)
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]))
Reference
この問題について(会議室の手配(グリンディ)), 我々は、より多くの情報をここで見つけました https://velog.io/@lsj8706/회의실-배정그리디テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol