LeetCode.1029-兩城排程(Two City Scheduling)

這是小川的第383次更新，第412篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第245題（順位題号是1029）。公司計劃采訪的人數為

2N

。将第

i

個人飛往城市A的費用是

[i][0]

，将第

i

個人飛到城市B的費用是費用

[i][1]

。

傳回将每個人帶到一個城市的最低費用，這樣每個城市就會有

N

個人到達。

例如：

輸入：[[10,20]，[30,200]，[400,50]，[30,20]]

輸出：110

說明：

第一個人去城市A，費用為10。

第二個人去城市A，費用為30。

第三個人去B市，費用為50。

第四個人去B市，費用為20。

總體最低費用為10 + 30 + 50 + 20 = 110，每個城市有一半的人在采訪。

注意：

• 1 <= costs.length <= 100
• 保證cost.length是偶數。
• 1 <=

  cost[i][0]

  ，

  cost[i][1]

  <= 1000

02 第一種解法

我們可以通過計算去A市、B市之間花費的內插補點

cost[i][0]-cost[i][1]

，來判斷哪一部分人去A市，哪一部分人去B市，內插補點最小的人去A市，因為內插補點越小，去A市是越省錢的。隻要把去A市的人确定了，剩下的都去B市就行。

結合題目的示例來看，原數組是

[[10,20]，[30,200]，[400,50]，[30,20]]

，計算去A市、B市之間花費的內插補點，數組變成了

[-10,-170,350,10]

，将內插補點數組排序後，得到

[-170,-10,10,350]

，前面的兩個內插補點去A市，後面的兩個內插補點去B市。其中內插補點最小的一組是

[30,200]

，它們的內插補點是-170，去A市比去B市少花170，是以去A市更加省錢。

思路：借助

Arrays

的

sort

方法，重寫

compare

方法，周遊按照內插補點排序後的數組，前一半元素取A市，後一半元素去B市，傳回累加的最小花費。

public int twoCitySchedCost(int[][] costs) {
    Arrays.sort(costs, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return (a[0] - a[1]) - (b[0] - b[1]);
        }
    });
    int sum = 0;
    for (int i = 0; i < costs.length; ++i) {
        if (i < costs.length / 2) {
            sum += costs[i][0];
        } else {
            sum += costs[i][1];
        }
    }
    return sum;
}
           

03 第二種解法

利用動态規劃來解，此方法來自讨論區，傳送門：https://leetcode.com/problems/two-city-scheduling/discuss/278731/Java-DP-Easy-to-Understand

public int twoCitySchedCost2(int[][] costs) {
    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++) {
            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];
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章251+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！