2285. Maximum Total Importance of Roads

HardView on LeetCode

Array Greedy Graph Sorting Heap (Priority Queue)

Time: O(n + E)

Space: O(n)

Intuition

Maximum road importance: assign values 1..n to roads. Road with highest degree gets highest value. Sort by degree.

Algorithm

1Count degree of each node. Sort degrees. Assign values 1..n to degrees ascending. Importance = sum(degree[i] * value[i]).

Common Pitfalls

•Greedy: highest degree node gets highest value. Sum of degree*value is the total importance.

2285.cs

// Approach: Sort cities by degree; assign highest values to highest-degree cities.
// Time: O(n + E) Space: O(n)

public class Solution
{
    public long MaximumImportance(int n, int[][] roads)
    {
        long ans = 0;

        long[] inDegree = new long[n];

        foreach (int[] road in roads)
        {
            int u = road[0];
            int v = road[1];
            inDegree[u]++;
            inDegree[v]++;
        }

        Array.Sort(inDegree);

        for (int i = 0; i < n; i++)
        {
            //Console.WriteLine("Index: " + (i + 1) + " Val: " + inDegree[i]);
            ans += (i + 1) * inDegree[i];
        }

        return ans;
    }
}

Was this solution helpful?