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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two City Scheduling

Difficulty: Medium

Problem Description

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti. Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Key Insights

  • The problem requires balancing the number of people sent to two different cities while minimizing the total cost.
  • A greedy approach is suitable, where we prioritize the individuals whose cost difference between the two cities is the largest.
  • Sorting the costs based on the difference between aCost and bCost allows us to make optimal decisions about where to send each person.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the costs array. Space Complexity: O(1) - we use a constant amount of space beyond the input.

Solution

To solve this problem, we will:

  1. Calculate the cost difference for each person between the two cities.
  2. Sort the array of costs based on this difference.
  3. Select the first n people to send to city A and the remaining n people to city B.
  4. Sum the costs for the selected individuals to get the minimum total cost.

Data structure used: Array for storing costs and differences.

Code Solutions

def twoCitySchedCost(costs):
    # Sort the costs based on the difference between aCost and bCost
    costs.sort(key=lambda x: x[0] - x[1])
    
    total_cost = 0
    n = len(costs) // 2
    
    # Select first n for city A and last n for city B
    for i in range(n):
        total_cost += costs[i][0]  # aCost for city A
    for i in range(n, 2 * n):
        total_cost += costs[i][1]  # bCost for city B
    
    return total_cost
← Back to All Questions