Two City Scheduling
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Example 1:
Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people
interviewing in each city.
Note:
1 <= costs.length <= 100- It is guaranteed that
costs.lengthis even. 1 <= costs[i][0], costs[i][1] <= 1000
class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, (a, b) -> {
return (a[0] - a[1]) - (b[0] - b[1]);
});
int sum = 0;
for (int i = 0; i < costs.length; ++i) {
if (i < costs.length / 2) {
sum += costs[i][0];
} else {
sum += costs[i][1];
}
}
return sum;
}
}Here, we are doing following steps..,
1) We need to sort costs based on its differences A cost and B cost. For that while sorting, we are finding cost differences between A and B and based on these differences all costs are sorted.
2) Now, for first half add cost of A and for next half add cost of B to result.
Also Check it:
Click here for April month challenges with solution and explanation
😍..Happy Coding...😍
Click Follow button to receive updates from us instantly.
Please let us know about your views in comment section.
Help Others, Please Share..!!!!
I did not understand the snippet:
ReplyDeleteArrays.sort(costs, (a, b) -> {
return (a[0] - a[1]) - (b[0] - b[1]);
Can you please explain it?
Thanks for asking. If we want to sort array of numbers either use sort() or we can sort using above snippet with a change in return a - b(sort array in ascending order). Likewise same, but here 2D so for sorting we can't use a[0] or a[1] alone, we need both. And based on differences it is sorted. If you still confused just add a print statement above return, then you will find working of it. Please do follow us to receive latest updates instantly. Happy Coding..!!
Delete