Fly Interviewees to Two Offices

MediumGreedy

Problem

A company invites 2n candidates to on-site interviews and wants exactly n of them in office A and n in office B. costs[i] = [costA, costB] is the price of flying candidate i to each office.

Return the minimum total travel cost.

Example 1

Input:
costs = [[15, 40], [60, 25], [30, 90], [70, 45]]
Output:
115

Candidates 0 and 2 to A (15 + 30), candidates 1 and 3 to B (25 + 45).

Example 2

Input:
costs = [[1, 2], [3, 4]]
Output:
5

Constraints

  • 2 ≤ costs.length ≤ 100, even
  • 1 ≤ costA, costB ≤ 1000

Hint

Show the first hint

Start by imagining everyone flies to B. What does it cost to move one candidate to A instead?

Walkthrough

How to approach it

01Clarify before coding

  • Must the split be exactly n and n? Yes.
  • Are costs positive? Yes, between 1 and 1000.
  • Do we return the assignment or the cost? Just the cost.

02Brute force

Try every way to choose which n candidates go to A.

Cost: C(2n, n) subsets, about 10^29 for 2n = 100.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.