Minimize travel cost with two cities
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are scheduling candidates to attend an onsite interview. Each candidate i can fly to New York for cost c1[i] or to San Francisco for cost c2[i].
Constraint: You must send exactly ceil(n/2) candidates to New York, and the remaining candidates to San Francisco.
Task: Compute the minimum possible total travel cost.
Additionally, write a few unit-style test cases that validate your solution (including edge cases such as n=1 and odd n).
Overview: Evaluates algorithmic skills in cost-optimization, greedy reasoning and sorting-based assignment while requiring correct handling of constraints and edge cases. Commonly asked in the Coding & Algorithms domain to test a candidate’s ability to design and implement a concrete, implementation-level algorithm and reason about correctness and complexity.
You are scheduling candidates for an onsite interview. For each candidate i, flying them to New York costs c1[i], and flying them to San Francisco costs c2[i]. You must send exactly ceil(n / 2) candidates to New York, where n is the total number of candidates, and send the remaining candidates to San Francisco.
Return the minimum possible total travel cost.
Constraints
- 1 <= n == len(c1) == len(c2) <= 200000
- 0 <= c1[i], c2[i] <= 10^9
Examples
Input: ([30], [5])
Expected Output: 30
Explanation: There is only one candidate, and ceil(1/2) = 1, so that candidate must go to New York even though San Francisco is cheaper.
Input: ([10, 30, 400, 30], [20, 200, 50, 20])
Expected Output: 110
Explanation: Send candidates 0 and 1 to New York, and candidates 2 and 3 to San Francisco. Total = 10 + 30 + 50 + 20 = 110.
Hints
- Try first assuming that everyone goes to San Francisco. Then ask: what is the extra cost or savings if a candidate is switched to New York?
- For candidate i, that switch changes the total by c1[i] - c2[i]. Which candidates should be chosen for New York?
Community answers
Answer by moreanuj1307
Leetcode problem 1029
We need to send exactly half the people to city A and half to city B while keeping the total cost as low as possible.
To do that, for each person we calculate the difference between the cost of city B and city A:
c2 - c1
This tells us which city is better for that person:
If the value is small or negative, city B is a better choice
If the value is large, city A is a better choice
After that, we sort everyone by this difference.
The first half of the sorted list is sent to city B
The second half is sent to city A
This works because sorting by the cost difference greedily places each person in the city where they provide the most savings relative to the other option.
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# Store:
# [cost difference between sending to city B vs city A, cost to A, cost to B]
# A smaller difference means sending to city B is relatively better.
diff = []
for c1, c2 in costs:
diff.append([c2 - c1, c1, c2])
# Sort people by the difference.
# People who benefit most from going to city B come first.
diff.sort()
res = 0
for i in range(len(diff)):
# First half goes to city B
if i < len(diff) // 2:
res += diff[i][2]
# Second half goes to city A
else:
res += diff[i][1]
return res
Answer by kavob60880
public class Solution {
public long solution(int[] c1, int[] c2) {
int n = c1.length, totalCost = 0;
PriorityQueue queue = new PriorityQueue<>((a, b) -> {
if( a[0] == b[0] ) {
return c1[a[1]] - c1[b[1]];
}
return a[0] - b[0];
});
for(int i = 0; i < n; i++) {
queue.offer(new int[]{c1[i] - c2[i], i});
}
for(int i = 0; i < (n + 1) / 2; i++) {
totalCost += c1[queue.poll()[1]];
}
while( !queue.isEmpty() ) {
totalCost += c2[queue.poll()[1]];
}
return totalCost;
}
}