BOJ 1931会議室の手配

質問する

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

解答方法

簡単です.所定の時間内にできるだけ多くの会議を開くためには、1回目の会議の開始時間が早ければ早いほど、会議が終わると次の会議が始まります.たとえば、会議のスケジュール(0,1)、(1,2)、(2,3)、および(1,3)があるとします.(0,1)、(1,3)にスケジュールするよりも(0,1)、(1,2)、(2,3)にスケジュールすると、より多くの会議が開かれます.筆者は2回のソートでこの問題を簡単に解決できる.

コード#コード#

import sys
input=sys.stdin.readline
n = int(input())
lis = [tuple(map(int,input().split())) for _ in range(n)]
a = sorted(lis,key=lambda x : (x[1],x[0]))

last = 0
cnt = 0
for i, j in a:
  
    if i >= last:
        cnt += 1
        last = j
        
print(cnt)