Two City Scheduling

Bloomberg

Google

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][0], and the cost of flying the i-th person to city B is costs[i][1].

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 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000

Solution:

Using a[0] - a[1] 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[0] - a[1]) - (b[0] - b[1]);
        // });
        
        Arrays.sort(costs, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return (a[0] - a[1]) - (b[0] - b[1]);
            }
        });
        
        int counter = 0, n = costs.length;
        for (int i = 0; i < n; i++) {
            if (i < (n / 2)) {
                counter += costs[i][0];
            } else {
                counter += costs[i][1];
            }
        }
        
        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][0] = dp[i - 1][0] + costs[i - 1][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][0];
                    continue;
                }
                dp[i][j] = Math.min(dp[i - 1][j - 1] + costs[i - 1][0], dp[i - 1][j] + costs[i - 1][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][0];
                    continue;
                }
                dp[j] = Math.min(dp[j - 1] + costs[i - 1][0], dp[j] + costs[i - 1][1]);
            }
            dp[0] = dp[0] + costs[i - 1][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][0] = dp[i - 1][0] + costs[i - 1][0];
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + costs[j - 1][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][0], dp[i][j - 1] + costs[i + j - 1][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][1];
        }
        dp[0] += costs[0][0];
        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][0], dp[j - 1] + costs[i + j - 1][1]);
            }
            dp[0] += costs[i][0];
        }
        return dp[n];
    }
}