Maximum Total Importance of Roads
You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.
You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.
You need to assign each city an integer value from 1 to n, where each value can only be used once. The importance of a road is defined as the sum of the values of the two cities it connects.
Return the maximum total importance of all roads possible after assigning the values optimally.
Example 1
Input
n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]Output
43Assigning values as [2, 4, 5, 3, 1] gives road importances 6, 9, 8, 7, 7, and 6 for a total of 43, which is optimal.
Example 2
Input
n = 5, roads = [[0,3],[2,4],[1,3]]Output
20Assigning values as [4, 3, 2, 5, 1] gives road importances 9, 3, and 8 for a total of 20, which is optimal.
Constraints
- 2 <= n <= 5 * 10^4
- 1 <= roads.length <= 5 * 10^4
- roads[i].length == 2
- 0 <= ai, bi <= n - 1
- ai != bi
- There are no duplicate roads.
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.