FastPrep
Problem · Array

Minimum Cost to Assign Candidates to Two Cities

Learn this problem
● Mediuminfosys logoinfosysFULLTIMEOA

Problem statement

You are given an even-length matrix costs, where costs[i][0] is the cost of sending candidate i to City A and costs[i][1] is the cost of sending that candidate to City B.

Send every candidate to exactly one city, with exactly half of the candidates assigned to each city.

Return the minimum possible total assignment cost.

Function

minimumTwoCityCost(costs: int[][]) → long

Examples

Example 1

costs = [[10,20],[30,200],[400,50],[30,20]]return = 110

Send candidates 0 and 3 to City A for 10 + 30, and candidates 1 and 2 to City B for 200 + 50 would cost 290. A cheaper valid split sends candidates 0 and 1 to City A and candidates 2 and 3 to City B, for 10 + 30 + 50 + 20 = 110.

Example 2

costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]return = 1859

One minimum-cost assignment sends candidates 0, 3, and 5 to City A, and candidates 1, 2, and 4 to City B.

Example 3

costs = [[1,100],[2,200]]return = 102

Send the first candidate to City B and the second candidate to City A, for a total cost of 100 + 2 = 102.

Constraints

  • 2 <= costs.length <= 100000
  • costs.length is even.
  • costs[i].length == 2
  • 0 <= costs[i][j] <= 1000000000
  • The minimum total cost fits in a signed 64-bit integer.

More infosys problems

drafts saved locally
public long minimumTwoCityCost(int[][] costs) {
    // write your code here
}
costs[[10,20],[30,200],[400,50],[30,20]]
expected110
checking account