Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1029. Two City Scheduling

Time: $O(n\log n)$

Space: $O(1)$

			


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;
  }
};




			


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;
  }
}




			


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))