2285. Maximum Total Importance of Roads

T: O(M + nlogn), M is edges length
S: O(n)

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        long[] inOutDegree = new long[n];
        for (int[] road : roads) {
            inOutDegree[road[0]]++;
            inOutDegree[road[1]]++;
        }
        Arrays.sort(inOutDegree);
        long result = 0;
        for (int i = 0; i < inOutDegree.length; i++) {
            result += (i+1)*inOutDegree[i];
        }
        return result;
    }
}

/**
4 + 12 + 20 + 6 + 1

count in + out degree 

T: O(M + nlogn), M is edges length
S: O(n)
 */