Two city scheduling

Array Greedy Sorting

68.4% acceptance

Feb 25, 2026

4873

366

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn two_city_sched_cost(costs: Vec<Vec<i32>>) -> i32 {
    let n = costs.len() / 2;
    let mut cs = costs;
    cs.sort_by_key(|c| c[0] - c[1]);
    cs[..n].iter().map(|c| c[0]).sum::<i32>() + cs[n..].iter().map(|c| c[1]).sum::<i32>()
  }
}