会議室を手配する

4441 ワード
グリディ テキストリンク

白駿1931


1つの会議室が最大でN個の会議を収容することができることを求めて、重複しません.
  • 会議が開始されると、途中で中断することはできません.1回の会議が終了すると、次の会議が開始されます.
  • 会議の開始時間と終了時間は同じかもしれません.この場合、最初から終わっていると考えられます.
  • 第1行は、会議数N(1≦N≦100000)を与える.2行目からN+1行目までは各会議の情報が与えられ、これはスペースであり、会議の開始時間と終了時間を与える.
  • 開始時間および終了時間は、2^31−1の自然数または0以下である.

    • にゅうしゅつりょく


    入出力11143506573859610818181122 1312144

    方法


    :(開始時間、終了時間)リストに保存し、終了時間を基準に昇順に並べ替えます.
    最初のエレメントの終了時間が変数に含まれ、リスト内で回転し、開始時間が設定した終了時間以上である場合、エレメントの終了時間に更新され、カウントが更新されます.-->間違っています.

    知るところ


    終了時間が同じ場合も考えます.
    終了時間が同じ場合は、クイック開始順にソートします.
    たとえば、
    2
    2 2
    1 2
    この場合、(2,2)に限ると1回の会議が可能であることを示しているが、ソートによりまず(12)を選択すれば(2)も選択可能であるため、2回の会議が可能である.
    そのため、終了時間の昇順、開始時間の昇順に並べ替えます!

    コード#コード#

    n = int(input())
graph = []
for _ in range(n):
    s, e = map(int, input().split())
    graph.append((s, e))
graph.sort(key=lambda x : (x[1], x[0]))

e = graph[0][1]
ans = 1
for i in range(1, len(graph)):
    if graph[i][0] >= e:
        ans += 1
        e = graph[i][1]
print(ans)
    dockerのデータボリュームとそのバックアップ方法
    [10655]一手