Bloomberg

2020-06-03

## 1029. Two City Scheduling

### Question:

There are `2N` people a company is planning to interview. The cost of flying the `i`-th person to city `A` is `costs[i]`, and the cost of flying the `i`-th person to city `B` is `costs[i]`.

Return the minimum cost to fly every person to a city such that exactly `N` people arrive in each city.

#### Example 1:

``````Input: [[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.
``````

Note:

1. `1 <= costs.length <= 100`
2. It is guaranteed that `costs.length` is even.
3. `1 <= costs[i], costs[i] <= 1000`

### Solution:

Using `a - a` to decide which should put into a. Then the rest should belong to b.

Time: O(nlogn) Space: O(1)

``````class Solution {
public int twoCitySchedCost(int[][] costs) {

// Similar way to sort the array

// Arrays.sort(costs, (a, b) -> {
//     return (a - a) - (b - b);
// });

Arrays.sort(costs, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return (a - a) - (b - b);
}
});

int counter = 0, n = costs.length;
for (int i = 0; i < n; i++) {
if (i < (n / 2)) {
counter += costs[i];
} else {
counter += costs[i];
}
}

return counter;
}
}
``````

Using DP to solve the question. DP[i][j] means there are currently i people, j people are in city A and i-j people are in city B.

Time: O(n^2) Space: O(n^2)

``````class Solution {
public int twoCitySchedCost(int[][] costs) {

// DP means i people in total, j people to city A and (i-j) people to city B
int n = costs.length;
int[][] dp = new int[n + 1][n/2 + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + costs[i - 1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j > n/2) continue;
// MIN To city A or city B
if (i == j) {
dp[i][j] = dp[i - 1][j - 1] + costs[i - 1];
continue;
}
dp[i][j] = Math.min(dp[i - 1][j - 1] + costs[i - 1], dp[i - 1][j] + costs[i - 1]);
}
}
return dp[n][n/2];
}
}
``````

It can also use 1-D array to reduce the space complexity.

``````class Solution {
public int twoCitySchedCost(int[][] costs) {
// 1-D array
int n = costs.length;
int[] dp = new int[n/2 + 1];

for (int i = 1; i <= n; i++) {

for (int j = i; j >= 1; j--) {
if (j > n/2) continue;
if (i == j) {
dp[j] = dp[j - 1] + costs[i - 1];
continue;
}
dp[j] = Math.min(dp[j - 1] + costs[i - 1], dp[j] + costs[i - 1]);
}
dp = dp + costs[i - 1];
}

return dp[n/2];
}
}
``````

DP[i][j] can also mean i people go to city A and j people go to city B.

``````class Solution {
public int twoCitySchedCost(int[][] costs) {
// DP means i people to cityA and j people to city B;
int n = costs.length / 2;
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + costs[i - 1];
}
for (int j = 1; j <= n; j++) {
dp[j] = dp[j - 1] + costs[j - 1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// MIN to city A or to city B
dp[i][j] = Math.min(dp[i-1][j] + costs[i + j - 1], dp[i][j - 1] + costs[i + j - 1]);
}
}
return dp[n][n];
}
}
``````

The following code reduces to 1-D array

``````class Solution {
public int twoCitySchedCost(int[][] costs) {
// 1-D array
int n = costs.length / 2;
int[] dp = new int[n + 1];
for (int j = 1; j <= n; j++) {
dp[j] = dp[j - 1] + costs[j - 1];
}
dp += costs;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// MIN to city A or to city B
dp[j] = Math.min(dp[j] + costs[i + j - 1], dp[j - 1] + costs[i + j - 1]);
}
dp += costs[i];
}
return dp[n];
}
}
``````