一応、時間計算量 \(O(N)\) での解法を書いておきます。

https://atcoder.jp/contests/abc194/submissions/20734963

仕事 A に、\(A_i\) が最小の人 \(i\) を使い、仕事 B に、\(B_j\) が最小の人 \(j\) を使うことを考えます。 これが可能ならば、最適性は明らかで、答は \(\max(A_i, B_j)\) です。

以下、そうでないとします。つまり \(i = j\) です。

最適解において、この人をどちらかの仕事には使うとしてよいです（そうでない割り当て \((A_k, B_l)\) が最適解だったとすると、\((A_k,B_i)\) も最適解です）。この人 \(i\) の様子で場合分けして、以下の \(3\) 種の値の最小値が答となります。

• 両方に人 \(i\) を使う場合のスコア：\(A_i + B_i\)
• 仕事 \(A\) のみ人 \(i\) を使う場合のスコア：\(\max(A_i, \min\{B_j\mid i\neq j\})\)
• 仕事 \(B\) のみ人 \(i\) を使う場合のスコア：\(\max(B_i, \min\{A_j\mid i\neq j\})\)

これをそのまま実装すると、時間計算量 \(O(N)\) にできると思います。