LeetCode 题解工作台
道路的最大总重要性
给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。 给你一个二维整数数组 roads ，其中 roads[i] = [a i , b i ] 表示城市 a i 和 b i 之间有一条 双向 道路。 你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们考虑每个城市对所有道路的总重要性的贡献度，记录在数组 中。然后将 按贡献度从小到大排序，为城市依次分配 $[1, 2, ..., n]$。 时间复杂度 $O(n \times \log n)$，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。
给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间有一条 双向 道路。
你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用 一次 。道路的 重要性 定义为这条道路连接的两座城市数值 之和 。
请你返回在最优安排下，所有道路重要性 之和 最大 为多少。
示例 1：
输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：43 解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。 - 道路 (0,1) 重要性为 2 + 4 = 6 。 - 道路 (1,2) 重要性为 4 + 5 = 9 。 - 道路 (2,3) 重要性为 5 + 3 = 8 。 - 道路 (0,2) 重要性为 2 + 5 = 7 。 - 道路 (1,3) 重要性为 4 + 3 = 7 。 - 道路 (2,4) 重要性为 5 + 1 = 6 。 所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。 可以证明，重要性之和不可能超过 43 。
示例 2：
输入：n = 5, roads = [[0,3],[2,4],[1,3]] 输出：20 解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。 - 道路 (0,3) 重要性为 4 + 5 = 9 。 - 道路 (2,4) 重要性为 2 + 1 = 3 。 - 道路 (1,3) 重要性为 3 + 5 = 8 。 所有道路重要性之和为 9 + 3 + 8 = 20 。 可以证明，重要性之和不可能超过 20 。
提示：
2 <= n <= 5 * 1041 <= roads.length <= 5 * 104roads[i].length == 20 <= ai, bi <= n - 1ai != bi- 没有重复道路。
解题思路
方法一：贪心 + 排序
我们考虑每个城市对所有道路的总重要性的贡献度，记录在数组 中。然后将 按贡献度从小到大排序，为城市依次分配 。
时间复杂度 ，空间复杂度 。
class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
deg = [0] * n
for a, b in roads:
deg[a] += 1
deg[b] += 1
deg.sort()
return sum(i * v for i, v in enumerate(deg, 1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N + M + N log N) where N is the number of cities and M is the number of roads, dominated by sorting cities. Space complexity is O(N) for storing degrees and assignments. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Expect discussion of greedy strategies based on city degree.
- question_mark
Look for correct handling of unique assignment constraints.
- question_mark
Check reasoning about why assigning top values to most connected cities maximizes importance.
常见陷阱
外企场景- error
Assigning values without considering city degree leads to suboptimal total importance.
- error
Ignoring the uniqueness constraint can produce invalid assignments.
- error
Failing to correctly sum both endpoints of each road causes miscalculation of total importance.
进阶变体
外企场景- arrow_right_alt
Minimize total importance instead of maximizing it by reversing value assignment.
- arrow_right_alt
Allow multiple roads between cities and compute maximum total importance accordingly.
- arrow_right_alt
Use weighted roads where each road has a factor, adjusting the greedy ranking by weighted degree.