1029. Two City Scheduling
Two City Scheduling (LeetCode 1029) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.
How to solve Two City Scheduling
Two City Scheduling is a Sorting-Based Greedy problem, part of Greedy Patterns. Solve greedy problems that require sorting as preprocessing step for optimal solutions.
Work towards the solution in these steps:
- Consider if a greedy approach can help minimize the total cost by making local optimal choices for sending people to cities.
- Think about how sorting the people based on some difference or ratio of costs might reveal a priority for assigning them to one city over the other.
- Try sorting the array by the difference between the cost to city A and city B, which could help decide who should definitely go to city A or city B.
The reference solution runs in O(n) time and O(1) space.
The Two City Scheduling solution and editorial walks through the full approach with reference code.
Problem statement
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.
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.
Example 2: Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] Output: 1859
Example 3: Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] Output: 3086
Constraints: 2 n == costs.length 2 <= costs.length <= 100 costs.length is even.
1 <= aCosti, bCosti <= 1000
Topics and companies
Topics: Greedy.
Reported in interviews at Bloomberg.
How to practise Two City Scheduling on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Two City Scheduling in the code editor, or read the Two City Scheduling editorial for a worked solution with its approach and complexity analysis.
Where Two City Scheduling sits in the DSA pattern sheet
Problems related to Two City Scheduling
Other problems that use the same Sorting Based and Greedy Patterns techniques:
- Assign Cookies — Easy, same subpattern
- Candy — Hard, same subpattern
- Hand of Straights — Medium, same subpattern
- Lemonade Change — Easy, same subpattern
- Merge Triplets to Form Target Triplet — Medium, same subpattern
- Queue Reconstruction by Height — Medium, same subpattern
Two City Scheduling FAQ
What is the LeetCode number of Two City Scheduling?
Two City Scheduling is LeetCode problem 1029, rated Medium.
What pattern is used to solve Two City Scheduling?
Two City Scheduling is a Sorting-Based Greedy problem. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.
What is the time complexity of Two City Scheduling?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Two City Scheduling?
Two City Scheduling has been reported in interviews at Bloomberg.