贪心题目：两地调度

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题两地调度出处1029. 两地调度难度4 级题目描述要求公司计划面试2n \texttt{2n}2n人。给定一个数组costs \texttt{costs}costs其中costs[i] [aCost i , bCost i ] \texttt{costs[i] [aCost}_\texttt{i}\texttt{, bCost}_\texttt{i}\texttt{]}costs[i] [aCosti​, bCosti​]表示第i \texttt{i}i人飞往 A 市的费用为aCost i \texttt{aCost}_\texttt{i}aCosti​飞往 B 市的费用为bCost i \texttt{bCost}_\texttt{i}bCosti​。返回当每个城市都有n \texttt{n}n人抵达的情况下将每个人都飞到其中一座城市的最低费用。示例示例 1输入costs [[10,20],[30,200],[400,50],[30,20]] \texttt{costs [[10,20],[30,200],[400,50],[30,20]]}costs [[10,20],[30,200],[400,50],[30,20]]输出110 \texttt{110}110解释第一个人去 A 市费用为10 \texttt{10}10。第二个人去 A 市费用为30 \texttt{30}30。第三个人去 B 市费用为50 \texttt{50}50。第四个人去 B 市费用为20 \texttt{20}20。最低总费用为10 30 50 20 110 \texttt{10} \texttt{30} \texttt{50} \texttt{20} \texttt{110}10305020110每个城市都有一半的人在面试。示例 2输入costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] \texttt{costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]}costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]输出1859 \texttt{1859}1859示例 3输入costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] \texttt{costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]}costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]输出3086 \texttt{3086}3086数据范围2 × n costs.length \texttt{2} \times \texttt{n} \texttt{costs.length}2×ncosts.length2 ≤ costs.length ≤ 100 \texttt{2} \le \texttt{costs.length} \le \texttt{100}2≤costs.length≤100costs.length \texttt{costs.length}costs.length为偶数1 ≤ aCost i , bCost i ≤ 1000 \texttt{1} \le \texttt{aCost}_\texttt{i}\texttt{, bCost}_\texttt{i} \le \texttt{1000}1≤aCosti​, bCosti​≤1000解法思路和算法为了计算每个城市都有n nn人抵达的最低费用可以首先计算全部2 n 2n2n人都抵达 A 市的总费用total \textit{total}total然后选其中n nn人换到 B 市更新总费用并使总费用最低。对于0 ≤ i 2 n 0 \le i 2n0≤i2n将第i ii人从 A 市换到 B 市之后总费用total \textit{total}total变成total ( bCost i − aCost i ) \textit{total} (\textit{bCost}_i - \textit{aCost}_i)total(bCosti​−aCosti​)。以下将每个人抵达 B 市的费用与抵达 A 市的费用之差称为费用差即费用差为bCost − aCost \textit{bCost} - \textit{aCost}bCost−aCost费用差可能是正数、零或负数。为了使总费用最低应使抵达 B 市的n nn个人的费用差之和最小化因此应选费用差最小的n nn个人。该做法是贪心策略贪心策略的正确性说明如下。假设全部2 n 2n2n人都抵达 A 市的总费用是total \textit{total}total费用差最小的n nn个人的费用差之和是x xx则费用差最小的n nn个人抵达 B 市的情况下总费用是total x \textit{total} xtotalx。如果选一个费用差更大的人抵达 B 市则需要替换费用差最小的n nn个人之一替换之后抵达 B 市的n nn个人的费用差之和一定大于等于x xx总费用一定大于等于total x \textit{total} xtotalx不可能有更低的总费用。因此选费用差最小的n nn个人可以使总费用最低。具体做法如下。计算全部2 n 2n2n人都抵达 A 市的总费用total \textit{total}total。创建长度为2 n 2n2n的数组differences \textit{differences}differences记录每个人的费用差对于0 ≤ i 2 n 0 \le i 2n0≤i2n计算differences [ i ] costs [ i ] [ 1 ] − costs [ i ] [ 0 ] \textit{differences}[i] \textit{costs}[i][1] - \textit{costs}[i][0]differences[i]costs[i][1]−costs[i][0]。将数组differences \textit{differences}differences按升序排序。遍历数组differences \textit{differences}differences的前n nn个元素即最小的n nn个元素对于0 ≤ i n 0 \le i n0≤in将total \textit{total}total更新为total differences [ i ] \textit{total} \textit{differences}[i]totaldifferences[i]。遍历结束之后的total \textit{total}total即为每个城市都有n nn人抵达的最低费用。代码classSolution{publicinttwoCitySchedCost(int[][]costs){inttotal0;intlengthcosts.length;intnlength/2;int[]differencesnewint[length];for(inti0;ilength;i){totalcosts[i][0];differences[i]costs[i][1]-costs[i][0];}Arrays.sort(differences);for(inti0;in;i){totaldifferences[i];}returntotal;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组costs \textit{costs}costs的长度的一半。数组costs \textit{costs}costs的长度是2 n 2n2n计算数组differences \textit{differences}differences需要O ( 2 n ) O ( n ) O(2n) O(n)O(2n)O(n)的时间将数组differences \textit{differences}differences排序需要O ( 2 n log ⁡ ( 2 n ) ) O ( n log ⁡ n ) O(2n \log (2n)) O(n \log n)O(2nlog(2n))O(nlogn)的时间排序之后遍历数组differences \textit{differences}differences的前n nn个元素需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度O ( n ) O(n)O(n)其中n nn是数组costs \textit{costs}costs的长度的一半。创建数组differences \textit{differences}differences需要O ( 2 n ) O ( n ) O(2n) O(n)O(2n)O(n)的空间将数组differences \textit{differences}differences排序需要O ( log ⁡ ( 2 n ) ) O ( log ⁡ n ) O(\log (2n)) O(\log n)O(log(2n))O(logn)的递归调用栈空间因此空间复杂度是O ( n ) O(n)O(n)。