整列図例[白俊1931号]

白駿「会議室の手配」問題

終了時間を優先的に昇順に並べ替えた後、終了時間が同じであれば、開始時間も昇順に並べ替えます.
最初は終わりの時間だけ並べ替えていましたが失敗してしまい、質問で反例を見たら直すことができました.
ソースコード

n=int(input())
timeline=[]
stack=[]
for i in range(n):
    s,e=map(int,input().split())
    timeline.append((s,e))

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

stack.append(timeline.pop(0))

while timeline:
    time=timeline.pop(0)
    if stack[-1][1]<=time[0]:
        stack.append(time)

print(len(stack))   

最初から.

timeline.sort(key=lambda x:x[1])

こうして終了した時間を並べ替えました.これにより、次の反例では、このような誤った答えが出力されます.(正解:5)

(五六)飛んで行ったのが見えます.開始時間を並べ替えていないので(6,6)先にpush,(5,6)条件に合わないため破棄される.
したがって,開始時間も以下のようにソートする.

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

修正の結果は以下の通りです.