LeetCode 1029. 两地调度

Categories:

题目描述
思路分析
1. 解法一：按差值排序（推荐）
相似题目

题目描述

✅ 1029. 两地调度

思路分析

解法一：按差值排序（推荐）

核心思路：

每个人去 A 或 B 的额外代价为 costA - costB。

将差值升序排序，前 n 人去 A，后 n 人去 B。

这样能保证总成本最小。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示人数。

空间复杂度：O(1)（忽略排序开销）。

import java.util.*;

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, Comparator.comparingInt(a -> a[0] - a[1]));

        int n = costs.length / 2;
        int sum = 0;
        for (int i = 0; i < costs.length; i++) {
            if (i < n) {
                sum += costs[i][0];
            } else {
                sum += costs[i][1];
            }
        }
        return sum;
    }
}

import "sort"

func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
    })

    n := len(costs) / 2
    sum := 0
    for i := 0; i < len(costs); i++ {
        if i < n {
            sum += costs[i][0]
        } else {
            sum += costs[i][1]
        }
    }
    return sum
}

相似题目

题目	难度	考察点
1029. 两地调度	中等	贪心
435. 无重叠区间	中等	贪心
646. 最长数对链	中等	贪心
1353. 最多可以参加的会议数目	中等	贪心 + 堆
1710. 卡车上的最大单元数	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/29540367