领扣LintCode算法问题答案-1895. 安排面试城市

领扣LintCode算法问题答案-1895. 安排面试城市

1895. 安排面试城市

描述

今天有 N 个面试者需要面试，公司安排了两个面试的城市A和B，每一个面试者都有到A城市的开销costA和到B城市的开销costB。公司需要将面试者均分成两拨，使得total cost最小。

• N是偶数
• 2 <= N <= 1e⁵
• 答案确保在int范围内
• 1 <= costA,costB <= 1e⁶

题目要求去A的人数和去B的人数相等。

样例 1：

输入: cost = [[5,4],[3,6],[1,8],[3,9]]
输出: 14
说明: 第一个和第二个人去B城市，剩下的去A城市

题解

public class Solution {
    /*** @param cost: The cost of each interviewer* @return: The total cost of all the interviewers.*/public int TotalCost(List<List<Integer>> cost) {
    // write your code hereCollections.sort(cost, new Comparator<List<Integer>>() {
    @Overridepublic int compare(List<Integer> o1, List<Integer> o2) {
    return (o1.get(0) - o1.get(1)) - (o2.get(0) - o2.get(1));}});int ret = 0;for (int i = 0; i < cost.size() / 2; i++) {
    ret += cost.get(i).get(0);}for (int i = cost.size() / 2; i < cost.size(); i++) {
    ret += cost.get(i).get(1);}return ret;}
}

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。