白駿1931号:会議室の手配

問題解決の考え方

ソートおよびグリッドアルゴリズム

はどのようにソートする必要がありますか?

✔前コード修正[タイムアウト+エラー]

import sys

N = int(input())

conf = {}
numbers = set()

for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    try:
        conf[a].append(b)
    except:
        conf[a] = [b]
        numbers.add(a)

if N == 1:
    print("1")
    sys.exit()

answer = 0
min_end = -1

for n in numbers:
    conf[n] = sorted(conf[n])

tf = 0
for n in numbers:
    count = 1
    same_count = 0

    start = n
    end = conf[start][0]

    if end < min_end or min_end == -1:
        min_end = end
    if start >= min_end and len(numbers) != 1:
        continue

    while end <= max(numbers):
        try:
            tmp = end
            end = conf[end][same_count]
            start = tmp
            count += 1
            if start == end:
                tf = 1
                same_count += 1
            else:
                same_count = 0
        except:
            same_count = 0
            end += 1
    if count > answer:
        answer = count

if tf:
    print(answer - 1)
else:
    print(answer)

が開始されると、開始時間を基準にソートし、終了時間を基準にソートする方法を選択しました.

はこのためにディック・シャナリーとトゥープを利用して、非常に複雑なコードを書き、「タイムアウト」を生んだ.

また,特殊な症例を扱うためにmin endやtf,in countなどの変数を随意に用いた.

このように乱雑にコードを補充した後、いくつかの特殊なケースが処理されたが、最終的にはすべてのエラーを修正できず、「エラー」を招いた.

このような複雑なコードの作成は、特殊なケースの処理がよくないことを認め、私の解釈が間違っていることを認め、方法を開いたはずです.しかし、そうしないで、このような汚いコードを完成しました.

✔修正後コード

N = int(input())
conf = []

for _ in range(N):
    start, end = map(int, input().split())
    conf.append([start, end])

conf = sorted(conf, key=lambda a: a[0]) #이렇게 처리하면, 원하는 요소를 기준으로 정렬할 수 있다.
conf = sorted(conf, key=lambda a: a[1])

last = 0
count = 0

for i, j in conf:
    if i >= last:
        count += 1
        last = j

print(count)

最終的にこの問題は、終了時間を基準として先にソートし、その後開始時間を基準としてソートすれば簡単に解決できる問題である.

一つの解法に夢中にならず、「考える」ことで解く習慣を身につけなければならないという教訓だ.

メソッドでエラーが発生すると、コードも複雑になり、特殊な場合は奇妙な方法で処理されるので注意してください.

手で問題を解くのではなく、頭で問題を解くように努力しましょう.
✔関連概念

問題に答える際の方向性選択の重要性!!

また,同じ日に解いた座標圧縮(標準30919733)問題においてもそれを感じた.
カウンタモジュール、Dictionary、Tuple、Set、Listなどの機能を適切に使用すると効率が向上します.
あまりにも不適切な場所に無理やり使う傾向がある.選択の練習が必要です!