Skip to content

1029. Two City Scheduling 👍

  • Time: $O(n\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int twoCitySchedCost(vector<vector<int>>& costs) {
    const int n = costs.size() / 2;
    int ans = 0;

    // How much money can we save if we fly a person to A instead of B?
    // To save money, we should
    //   1) fly the person with the max saving to A
    //   2) fly the person with the min saving to B
    sort(begin(costs), end(costs), [](const auto& a, const auto& b) {
      // Sort in descending order by the money saved
      // If we fly a person to A instead of B
      return a[1] - a[0] > b[1] - b[0];
    });

    for (int i = 0; i < n; ++i)
      ans += costs[i][0] + costs[i + n][1];

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int twoCitySchedCost(int[][] costs) {
    final int n = costs.length / 2;
    int ans = 0;

    // How much money can we save if we fly a person to A instead of B?
    // To save money, we should
    //   1) fly the person with the max saving to A
    //   2) fly the person with the min saving to B

    // Sort in descending order by the money saved if we fly a person to A instead of B
    Arrays.sort(costs, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

    for (int i = 0; i < n; ++i)
      ans += costs[i][0] + costs[i + n][1];

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def twoCitySchedCost(self, costs: List[List[int]]) -> int:
    n = len(costs) // 2

    # How much money can we save if we fly a person to A instead of B?
    # To save money, we should
    #   1) fly the person with the max saving to A
    #   2) fly the person with the min saving to B

    # Sort in descending order by the money saved if we fly a person to A
    costs.sort(key=lambda x: x[0] - x[1])
    return sum(costs[i][0] + costs[i + n][1] for i in range(n))