LeetCode 1029: Two City Scheduling Solution

Master LeetCode problem 1029 (Two City Scheduling), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1029. Two City Scheduling

Medium

Array Greedy Sorting

Problem Explanation

Explanation:

To minimize the total cost, we need to send n people to city A and n people to city B. We can achieve this by sorting the costs based on the difference between the costs of sending a person to city A and city B. We then send the first n people with the smallest differences to city A and the rest to city B.

Steps:

Calculate the cost difference for each person (cost of sending to city A - cost of sending to city B).
Sort the costs based on the cost difference.
Send the first n people to city A and the rest to city B.

Time Complexity: O(n log n) - Sorting the costs Space Complexity: O(n) - for storing the cost differences

Solution Code

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int totalCost = 0;
        int[] costDiff = new int[costs.length];

        for (int i = 0; i < costs.length; i++) {
            costDiff[i] = costs[i][0] - costs[i][1];
            totalCost += costs[i][1]; // Add costs of sending everyone to city B
        }

        Arrays.sort(costDiff);

        for (int i = 0; i < n; i++) {
            totalCost += costDiff[i]; // Add costs of sending n people to city A
        }

        return totalCost;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1029 (Two City Scheduling)?

This page provides optimized solutions for LeetCode problem 1029 (Two City Scheduling) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1029 (Two City Scheduling)?

The time complexity for LeetCode 1029 (Two City Scheduling) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1029 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1029 in Java, C++, or Python.

Back to LeetCode Solutions