Show problems as
Classic problem #1029MediumArrayGreedySortingHungarian AlgorithmSuccessive Shortest Path Algorithm

Two City Scheduling

Real-world version: Splitting the Crew Between Two Hubs
Tracked in this browser only
Read Two City Scheduling on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A maintenance contractor has 2 * n engineers on the roster and two depots that each need staffing for the week: the northern hub and the southern hub. Exactly n engineers go to the northern hub and the other n go to the southern hub.

You are given costs, where costs[i] = [north_i, south_i]. Sending engineer i to the northern hub costs north_i in travel allowance, and sending that same engineer to the southern hub costs south_i instead.

Return the smallest total allowance the contractor can pay while filling both hubs with exactly n engineers each.

Examples

Example 1

Input
costs = [[16, 90], [270, 44], [55, 61], [820, 35]]
Output
150

Sending engineers 0 and 2 north costs 16 and 55, and sending engineers 1 and 3 south costs 44 and 35, for a total of 150. Two engineers reach each hub, as required.

Example 2

Input
costs = [[7, 9], [9, 7]]
Output
14

One engineer must go to each hub. Sending engineer 0 north for 7 and engineer 1 south for 7 costs 14 in all.

Example 3

Input
costs = [[1, 1000], [2, 1000], [3, 1000], [4, 1000]]
Output
2003

Two engineers still have to travel south at 1000 each. Sending engineers 0 and 1 north for 1 and 2 brings the total to 2003.

Constraints

  • 2 * n == costs.length
  • 2 <= costs.length <= 100
  • costs.length is even.
  • 1 <= north_i, south_i <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def two_city_sched_cost(costs: list[list[int]]) -> int:
Java
public int twoCitySchedCost(int[][] costs)

More on the same topics