Maximum Total Importance of Roads
MediumGreedyGraphSortingHeap (Priority Queue)
Solution
export function maximumImportance(n: number, roads: number[][]): number {
const degrees = new Array(n).fill(0);
for (const [a, b] of roads) {
degrees[a] += 1;
degrees[b] += 1;
}
return degrees.sort((a, b) => a - b).reduce((acc, degree, i) => acc + degree * (i + 1), 0);
}
Complexity
- Time:
O(n * logn)
- Space:
O(n)