LeetCode 1029. Two City Scheduling
2020-06-03 23:13:02 # leetcode # greedy

Problem

LeetCode 1029. Two City Scheduling

1. 题目简述

公司有2N个面试者，一共有两个面试地点A和B，需要保证每个地点都有N个人面试，每个面试者距离AB远近不同，导致路程花销也不一样。每个人的到达A、B地点的花销用一个二维数组来表示，求怎么样分配使得总花销最小，求出这个总花销。例如：

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.

限制：

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

2. 算法思路

首先最直接的办法使用DFS，回溯，遍历所有可能性，时间复杂度为O(2^n)，这里n为总人数，由于n在最大为100，因此这个方法一定会超时，放弃。

那么能否使用DP呢？也不行！因为要求每个面试地点都要有N个人，也就是说前面的选择对后面的选择会造成影响，说明问题不算独立子问题，所以也不行。

这里我们使用贪心法。

贪心法

公司希望总花销最小，其实这不单单是从整体的角度考虑，更要从个人的角度去看，对于每个人来说，都有两种选择，A和B，而每个人到A和到B的花销的差其实才是我们最关心的，如果差的特别多，比如说cost[i][0]很小，而cost[i][1]很大，那么我们就应该选择A地点，因为如果选择B地点的话，就会多花出很多钱。

我们定义一个变量叫做营收S，对于A的营收S(A) = cost[i][0] - cost[i][1]，这个营收S可能为正，也可能为负，如果为正，就说明到A的cost比到B的cost要多，我们将他分配到A地点的可能性就更小；相反若为负，则可能性更大。

因此我们将每个数对按照对A的营收进行排序，前N个元素就为A地点的面试人，剩下的就是B地点的面试人。

时间复杂度:O(nlogn)，排序的复杂度。

空间复杂度:O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // 不能用DP，因为有N个的限制，状态有依赖关系？每个只有两种选择的可能性，使用backtracking + 剪枝？也不行，因为可能性实在是太多了，不可能全都穷举完，cost的length达到了100。考虑使用贪心。
        Arrays.sort(costs, (a1, a2) -> (a1[0] - a1[1]) - (a2[0] - a2[1]));
        int n = costs.length / 2, minCost = 0;

        for (int i = 0; i < n; i++) {
            minCost += costs[i][0] + costs[i + n][1];
        }

        return minCost;

    }
}
Prev
2020-06-03 23:13:02 # leetcode # greedy
Next