← Back to Index

📚 Two City Scheduling – Java Cheat Sheet

📌 What Is It?

The Two City Scheduling problem involves sending 2N people to two cities such that exactly N people go to each city, and the total cost is minimized. Each person has a cost for traveling to either city.

🧱 Pattern Template

Greedy Algorithm

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // Sort by the difference in costs between the two cities
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int totalCost = 0;
        int n = costs.length / 2;

        // Send the first N people to city A and the rest to city B
        for (int i = 0; i < costs.length; i++) {
            if (i < n) {
                totalCost += costs[i][0]; // City A
            } else {
                totalCost += costs[i][1]; // City B
            }
        }

        return totalCost;
    }
}

▶️ View Animation

📊 Time Complexity

• Sorting: O(N log N), where N is the number of people.
• Greedy Selection: O(N), for iterating through the sorted array.
• Total Complexity: O(N log N).

✅ Use Cases

• Minimizing costs in resource allocation problems.
• Solving problems involving balanced partitioning.

📘 Common LeetCode Problems

• 1029. Two City Scheduling [Medium] Greedy

🧪 Example

Input: costs = [[10,20],[30,200],[50,30],[20,50]]
Output: 110

Explanation:
- Send person 0 and 3 to city A: 10 + 20 = 30
- Send person 1 and 2 to city B: 200 + 30 = 230
- Total cost = 30 + 230 = 110

💡 Pro Tips

• Sort the array by the cost difference between the two cities to prioritize the cheaper option.
• Ensure exactly N people are sent to each city by dividing the sorted array.
• Use a greedy approach to minimize the total cost efficiently.