The O(n) Club: Two City Scheduling: Greed, Sorting, and Not Getting Yelled At By Accounting

The O(n) Club: Two City Scheduling—Greed, Sorting, and Not Getting Yelled At By Accounting

⚡ TL;DR

Got an even number of people and two cities? Don’t overthink it: sort everyone by how much cheaper it is to send them to City A instead of City B, dump the first half into City A, second half into B, and watch your travel budget shrink without tears. For masochists, here’s how NOT to do it:

// Brute force works—if you have eternity
int minCost = Integer.MAX_VALUE;
// Try all possible half-and-half combinations... get comfy

🧠 How Devs Usually Mess This Up

It’s tempting to send everyone to their cheapest city. Oops—now City A is packed and City B is a ghost town, and your constraints are as broken as your unit tests. Next, you might break out some dynamic programming wizardry or start backtracking feverishly. Put down the recursion: greedy sorting nails it in seconds.

And don’t just sort by who’s cheap for City A (or B) alone. The real deal is the cost difference: it’s about the relative savings, not the total. Sort by costA - costB, not costA or costB, unless you enjoy debugging budget deficits.

🔍 What’s Actually Going On

Imagine you’re splitting your dev team between Snowville and Sunnytown for a conference—exactly half to each (this is mandatory, not an improv game!). The ones who would lose you the most extra money by going to Sunnytown go to Snowville, and vice versa. Sorting by cost difference makes sure your cash stays warm.

The basic idea: those with negative (costA – costB) travel cheaper to A; positive diff, to B. Rinse, sort, assign. It’s like optimizing snack selection among picky eaters—let the ones violently opposed to raisins have the cookies.

🛠️ PseudoCode

• For every person, calculate costA - costB.
• Sort the whole crew by this difference (smallest to largest).
• Send the first n to City A—they either love it or hurt the budget least.
• The remaining n go to City B—less regret that way.
• Sum up their respective costs for each city and breathe easy.

// Java pseudocode
// Given int[][] costs (costA, costB):
// 1. Sort by (costA - costB)
// 2. Assign first n to A, rest to B

💻 The Code

import java.util.*;
 public class TwoCityScheduling {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int n = costs.length / 2, total = 0;
        for (int i = 0; i < n; i++) total += costs[i][0]; // City A
        for (int i = n; i < 2 * n; i++) total += costs[i][1]; // City B
        return total;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Exact split: Half to each city—if you forget, the universe (or the test suite) will punish you.
• Sorting by wrong number: Sorting by just costA or costB mangles the result. costA - costB or bust.
• Bad inputs: Odd number of people? Congrats, your problem’s now a real interview nightmare.
• Complexity: O(n log n) to sort, O(n) to tally. Easy as Java gets—no Big O flexing required.

🧠 Interviewer Brain-Tattoo

“Sort by what matters, assign by the rules, and your budget (and code reviewer) won’t scream.”