[白俊]1931会議室(銀色2)-Pythonを手配

質問する

https://www.acmicpc.net/problem/1931
会議室があり、それを使用するN個の会議について、会議室使用表を作成します.各会議Iには、開始時間と終了時間があり、各会議が重複しないように、会議室の最大数を見つけます.しかし、会議が始まると、途中で中断することはできません.一つの会議が終わると同時に、次の会議が始まる可能性があります.会議の開始時間と終了時間は同じかもしれません.この場合、最初から終わっていると考えられます.

入力

1行目には、会議数N(1≦N≦100000)が与えられる.2行目からN+1行目までは各会議の情報が与えられ、これはスペースであり、会議の開始時間と終了時間を与える.開始時間および終了時間は、231−1の自然数または0以下である.

しゅつりょく

最初の行の最大使用可能な会議数を出力します.

に答える

最初は開始時間順に並べて入れればいいんですよね?開始時間が最も速い会議が一日中会議を開くように手配されると、その日は会議室で1つの会議しか開かない.
だから、終了時間を基準に並べ替えて、開始時間を基準に並べ替えておけば、1つの会議は時間を無駄にせずにできるだけ多くの会議ができると思います.

meetings = []
for _ in range(n):
    s, e = map(int, input().split())
    meetings.append((s, e))

まず、会議の開始時間と終了時間を会議に記録します.

meetings.sort(key=lambda x: (x[1], x[0]))

lambdaを用いてsortのソート基準を종료 시간→시작 시간とする

cnt, last_end = 0, 0
for start, end in meetings:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)

また、会議の開始時間が現在進行中の会議の終了時間の後である場合は、cntを追加し、その会議の終了時間をlast endに繰り返す必要があります.
そしてfor loop印刷cntを回して終わりました!

完全なコード

meetings = []
for _ in range(n):
    s, e = map(int, input().split())
    meetings.append((s, e))

meetings.sort(key=lambda x: (x[1], x[0]))

cnt, last_end = 0, 0
for start, end in meetings:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)