1029. Two City Scheduling

题目信息

题号:

1029

难度:

Medium

主题:

人员分配、双城市、最小总费用

原题:

LeetCode 1029

重点:

输入包含 2n 个人,必须恰好安排 n 人去 A 城、n 人去 B 城,并最小化全部出行费用

题目重述

给定费用矩阵 costs,其中 costs[i] = [a_i, b_i] 表示第 i 个人前往 A 城和 B 城的费用。总人数为偶数,记为 2n。

必须把每个人安排到且仅安排到一个城市,并保证两个城市各接收恰好 n 人。请返回满足人数约束时所有人的最小总出行费用。

2 <= costs.length <= 100 且长度为偶数,1 <= a_i, b_i <= 1000。

自建示例

选择个人费用差异较大的城市:

输入:costs = [[30,70],[80,20],[40,60],[90,10]]
输出:100
解释:安排第 0、2 人去 A 城,费用为 30 + 40;安排第 1、3 人去 B 城,费用为 20 + 10,总费用为 100。

只有两个人:

输入:costs = [[5,100],[7,9]]
输出:14
解释:两个城市各需一人。第 0 人去 A 城花费 5,第 1 人去 B 城花费 9,总费用为 14。