aboutsummaryrefslogtreecommitdiff
path: root/max_total_importance_road.cpp
blob: 82380abf0d8b47b149dd79459d67446e5375b81a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 2285. Maximum Total Importance of Roads
#include "leetcode.h"

/*
 * 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}', where each value can only be used once. the
 * importance of a road is then 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.
 */

class Solution {
public:
  long long maximumImportance(int n, vector<vector<int>> &roads) {
    long long cnt[50001] = {}, ans = 0;
    for (auto &i : roads) {
      ++cnt[i[0]];
      ++cnt[i[1]];
    }
    sort(begin(cnt), begin(cnt) + n);
    for (int i = 0; i < n; i++)
      ans += cnt[i] * (i + 1);
    return ans;
  }
};

int main() {
  Solution obj;
  vvd r1 = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}};
  vvd r2 = {{0, 3}, {2, 4}, {1, 3}};
  printf("%lld\n", obj.maximumImportance(5, r1)); // expect: 43
  printf("%lld\n", obj.maximumImportance(5, r2)); // expect: 20
}