【ABC194 B】「Job Assignment」を解く【Python3】

受注した仕事Aと仕事Bの従業員への割り当てを考えたとき、2つの仕事が終わるのにかかる時間の最小値を求める問題です。

提出

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
ans = 10**6

for i in range(n):
    for j in range(n):
        if i == j:
            ans = min(ans, sum(ab[i]))
        else:
            ans = min(ans, max(ab[i][0], ab[j][1]))

print(ans)

Nが1000と少ないので仕事Aと仕事Bの割り当ての全探索をすることにします。

それぞれの従業員の仕事にかかる時間 A_i, B_i を内包リストに入れておきます。

for文を用いて、割り当てをすべて試します。

i,j が同じ場合は、一人が両方の仕事をしているので、合計値を求めます。

それ以外では、時間の長い方の分だけかかるため、大きい方を取得します。

そのつど、「ans」と比較して、小さい方を入れていき、最終的に「ans」を出力します。