会議室の手配(1931)

3922 ワード
greedy 白駿 テキストリンク

Greedy + Sort


質問する


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

入力


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

しゅつりょく


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

n = int(sys.stdin.readline())
meetings = sorted([list(map(int, sys.stdin.readline().split())) for i in range(n)], key = lambda x: (x[1], x[0]))

end = 0
count = 0

for m in meetings:
    if end <= m[0]:
        end = m[1]
        count += 1
        
print(count)
Greyと適切に並べ替えの問題を考えなければならない.
入力した時間順にスケジュールを並べます->開始した時間順に並べます.
参照)
https://dojinkimm.github.io/problem_solving/2019/09/30/boj-1931-meeting.html
https://daimhada.tistory.com/38
JavaScript #28
[コードスパルタ]アプリケーション開発総合クラス4週間