two-city-scheduling

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A company is planning to interview <code>2n</code> people. Given the array <code>costs</code> where <code>costs[i] = [aCosti, bCosti]</code>,&nbsp;the cost of flying the <code>ith</code> person to city <code>a</code> is <code>aCosti</code>, and the cost of flying the <code>ith</code> person to city <code>b</code> is <code>bCosti</code>.

Return the minimum cost to fly every person to a city such that exactly <code>n</code> people arrive in each city.

&nbsp;
Example 1:

<pre>
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
</pre>

Example 2:

<pre>
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
</pre>

Example 3:

<pre>
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 * n == costs.length</code></li>
	<li><code>2 &lt;= costs.length &lt;= 100</code></li>
	<li><code>costs.length</code> is even.</li>
	<li><code>1 &lt;= aCosti, bCosti &lt;= 1000</code></li>
</ul>

twoCitySchedCost

Two City Scheduling

Rearrange Array to Maximize Prefix Score

rearrange-array-to-maximize-prefix-score

重排数组以得到最大前缀分数

Greedy

Array

Sorting

公司计划面试 <code>2n</code> 人。给你一个数组 <code>costs</code> ，其中 <code>costs[i] = [aCosti, bCosti]</code> 。第 <code>i</code> 人飞往 <code>a</code> 市的费用为 <code>aCosti</code> ，飞往 <code>b</code> 市的费用为 <code>bCosti</code> 。

返回将每个人都飞到 <code>a</code> 、<code>b</code> 中某座城市的最低费用，要求每个城市都有 <code>n</code> 人抵达。

 

示例 1：

<pre>
输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
</pre>

示例 2：

<pre>
输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
输出：1859
</pre>

示例 3：

<pre>
输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
输出：3086
</pre>

 

提示：

<ul>
	<li><code>2 * n == costs.length</code></li>
	<li><code>2 <= costs.length <= 100</code></li>
	<li><code>costs.length</code> 为偶数</li>
	<li><code>1 <= aCosti, bCosti <= 1000</code></li>
</ul>