[BOJ]1931-会議室の手配

展開

に近づく

の無条件終了時間の最も早い会議を選択することは有利である.

しかし、会議の開始時間は既存の選択された会議と衝突してはならない.

これらの考え方自体は難しくはないが,実施中に試行錯誤を繰り返したため,いくつかの工夫がなされた.
まず,所与の範囲内で最小終了時間を持つ会議の関数を再帰的に呼び出すことにより,0<=T<=2^{31}−10<=T<231̴1という不気味な時間範囲とO(n 2)O(n 2)O(n 2)に達する時間複雑度により,失敗した.

コード1-恐ろしいヘルメットセットコード

from sys import stdin

N = int(stdin.readline())
INT_MAX = 2**32

def search(begin, end):
    global N, INT_MAX, time_max, meetings

    res = 0
    next_begin = begin
    min_end_time = begin

    for i in range(begin, end):
        if meetings[i] < min_end_time:
            min_end_time = meetings[i]
            next_begin = begin
            res += 1
    
    next_end = meetings[next_begin] if meetings[next_begin] != INT_MAX else time_max

    return res + search(next_begin, next_end)

time_max = 0
meetings = [INT_MAX for _ in range(INT_MAX)]

for _ in range(N):
    a, b = tuple(int(i) for i in stdin.readline().rstrip().split())
    if b > meetings[i]:
        meetings[i] = b
    
    if b > time_max:
        time_max = b

print(search(0, meetings[0]))

会議をmeetingsの形でmeetings[시작 시간] = 종료 시간のアレイに格納し、会議の開始時間を昇順に並べ、その後、候補群会議の開始から終了時間までの範囲内でより早く終了した会議を再帰的に検索する.
簡単に例を使用できますが、会議時間が増加(=配列長が増加)、会議数が増加(=探索候補者の増加)すると、時間とメモリのオーバーシュートが頻繁に発生します.
何日か悩んだ末、ようやく質問検索欄に入り、大きなヒントを得ました(…).

コード2-ソートおよびナビゲーション用のコード

from sys import stdin

N = int(stdin.readline())
jobs = [[int(i) for i in stdin.readline().split()] for _ in range(N)]
jobs.sort(key=lambda x:(x[1], x[0]))

count = 0
prev_end = 0

for begin, end in jobs:
    if begin >= prev_end:
        count += 1
        prev_end = end

print(count)

会議リストが(1位:終了時刻、2位:開始時刻)の昇順に並べられている場合は、1つの繰り返し文だけですべての問題を解決できます.私たちが関心を持っているのは、次の会議が前の会議と重なるかどうかを確認することだけです.

ヒント

N<=100000の範囲に圧倒されました(…)コストが高いと思われるソート方法を簡単に適用することはできないが,よりコストの高いコードが生成され,あがきながら正解を見つけた.
タッチソフトに負担はありません.他の分野とは異なり、実際に失敗した場合の資源損失はないからです.いろいろ試してみると大きなメリットがあると思います
私は今、このような良い特性をよく利用しているのではないでしょうか.もっと激しく試してみてもいいですよね?挑戦は変化するが、動かなければ何も起こらない.仕事に没頭するのではなく、何とかして何かを書いて実行しなさい.少なくとも符号化の面ではもう少し勝手に(…)もう時間だと思います.