会議室を手配する

質問する

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

入力

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

しゅつりょく

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

ソリューション

これは

グリディ方式の古典的な問題で、グリディを知らないので苦労した.

の最適な会議時間を探すために、まずソートされたランダを利用して開始時間を基準にソートし、終了時間を基準にソートします.

のように、終了時間順に並べ替えられるが、終了時間が同じである場合、開始時間はより速い順に並べ替えられる.

では、最初の会議の終了時間を開始点として入力し、繰り返し文で、次の会議の開始時間が開始時間以上である場合、cnt+1となり、その会議の終了時間を開始時間に更新する.

失敗コード

n = int(input())
room = []

for i in range(n):
    a, b = map(int, input().split())
    room.append([a, b])

room.sort(key = lambda x: x[0])
room.sort(key = lambda x: x[1])
print(room)
cnt = 1
end = room[0][1]
for i in range(1, n):
    if room[i][0] >= end:
        cnt += 1
        end = room[i][1]

print(cnt)

パスコード

import sys
n = int(sys.stdin.readline())
lst = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]


#시작시간을 기준으로 선정렬 
lst.sort(key=lambda x:x[0])

#종료시간 기준으로 정렬 
lst.sort(key = lambda x:x[1])

#이렇게 정렬했을 때 종료시간이 같을 때 시작시간 오름차순으로 정렬된다. 

cnt = 1
#첫회의의 시작점이 기준 
conference = lst[0][1] 
#두번째 회의부터 돌면서 
for i in range(1,n) :
    #다음회의 시간의 시작이 현재 종료보다 크거나 같으면 cnt += 1 
    if lst[i][0] >= conference:
        cnt +=1
        #그 회의의 종료시간을 기준으로 갱신 
        conference = lst[i][1]
print(cnt)