Two City Scheduling Leetcode Problem 1029 [Python Solution]

Problem Overview

In the Two City Scheduling Leetcode problem, a company is planning to interview 2n people, and they are given an array costs.

Here, costs[i] = [aCosti, bCosti] represents the cost of flying the ith person to city A (aCosti) or to city B (bCosti).

The goal is to minimize the total cost while ensuring that exactly n people arrive in each city.

Example 1:

Input:costs = [[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.

Constraints:

• 2 * n == costs.length
• 2 <= costs.length <= 100
• 1 <= aCosti, bCosti <= 1000

Efficient Approach with Sorting

To solve this problem efficiently, we can follow a greedy approach.

We’ll calculate the cost difference for each person between flying to city B and flying to city A.

This difference will represent the additional cost incurred by sending the person to city B.

We’ll sort the persons based on this cost difference in ascending order.

Then, we’ll send the first half of the sorted list to city B and the remaining half to city A.

This way, we minimize the total cost.

Here’s the efficient Python code solution:

def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        diffs = []  # List to store cost differences
        for c1, c2 in costs:
            diffs.append([c2 - c1, c1, c2])

        diffs.sort()  # Sort the persons based on cost difference
        res = 0  # Initialize the total cost

        for i in range(len(diffs)):
            if i < len(diffs) // 2:
                res += diffs[i][2]  # Send to city B
            else:
                res += diffs[i][1]  # Send to city A

        return res

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of persons to be scheduled.

Reasoning Behind Our Approach

The reasoning behind this approach is to minimize the total cost while ensuring that the number of people sent to city A and city B is balanced.

By calculating the cost difference for each person, we prioritize sending those with lower cost differences to city B, as it results in a lower additional cost.

This approach efficiently identifies the optimal assignment of persons to cities.

Related Interview Questions By Company:

• Maximum Twin Sum Of A Linked List LeetCode
• Surrounded Regions LeetCode
• Meeting Rooms II LeetCode

Related Interview Questions By Difficulty:

• Jump Game II LeetCode
• Maximum Sum Circular Subarray LeetCode
• Partition Labels LeetCode

Related Interview Questions By Category:

• Combination Sum Iv LeetCode
• First Missing Positive LeetCode
• Design Browser History LeetCode

Conclusion

In this blog post, we’ve discussed the Two City Scheduling problem, where the goal is to minimize the total cost of flying 2n people to two cities while ensuring an equal number of people in each city.

We’ve presented an efficient Python solution that utilizes a greedy approach with sorting to achieve the desired outcome.

This solution has a time complexity of O(n log n).

You can find the full code and explanations in the previous sections.

If you found this blog post helpful, please like and engage to support the our platform.

For further support, consider checking out our Patreon.

Feel free to ask questions, make suggestions, or share your thoughts in the comments.

You can also access the LeetCode problem description here.

Happy coding!