We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Two City Scheduling

Number: 1095

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Meta, Amazon, TikTok

Problem Description

Given 2n people and their respective costs for traveling to two cities A and B, find the minimum total cost to send exactly n people to each city. Each person has a cost profile [aCost, bCost] representing the cost of sending them to city A or city B.

Key Insights

  • Sort the cost array based on the difference (aCost - bCost).
  • Sending a person to city A saves money when aCost is much lower than bCost, and vice versa.
  • By sorting the array, the optimal decision is to send the first n people (with greatest relative savings for city A) to city A and the remaining n people to city B.
  • The greedy approach minimizes total cost by maximizing cost differences.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array of 2n elements. Space Complexity: O(1) if in-place sorting is allowed, otherwise O(n) for the sorted array copy.

Solution

The solution uses a greedy algorithm. First, we compute the difference between the cost of going to city A and city B for each person. We sort the list of costs based on this difference. The intuition is that if a person is much cheaper to send to city A than to city B (i.e., a very negative difference), they should go to city A. Conversely, if the cost for city B is significantly lower, they should be allocated there. After sorting, we assign the first n people to city A and the remaining n people to city B, ensuring that the balance of people in each city is maintained. This approach guarantees that the total cost is minimized.

Code Solutions

def twoCitySchedCost(costs):
    # Sort costs by the difference between aCost and bCost
    costs.sort(key=lambda cost: cost[0] - cost[1])
    
    total_cost = 0
    n = len(costs) // 2  # Each city gets n people
    # Send first n people to city A
    for i in range(n):
        total_cost += costs[i][0]
    # Send remaining n people to city B
    for i in range(n, 2 * n):
        total_cost += costs[i][1]
    return total_cost

# Example usage:
costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))  # Expected output: 110
← Back to All Questions