diff options
-rw-r--r-- | max_total_importance_road.c | 29 | ||||
-rw-r--r-- | max_total_importance_road.cpp | 34 | ||||
-rw-r--r-- | max_total_importance_road.py | 37 |
3 files changed, 90 insertions, 10 deletions
diff --git a/max_total_importance_road.c b/max_total_importance_road.c index 145c3e2..55c9e07 100644 --- a/max_total_importance_road.c +++ b/max_total_importance_road.c @@ -1,12 +1,20 @@ // 2285. Maximum Total Importance of Roads -#include <stdio.h> -#include <stdlib.h> +#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. + */ int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } long long maximumImportance(int n, int **roads, int roadsSize, int *roadsColSize) { - long long ans = 0, *timeShown = calloc(n, sizeof(long long)); + long long ans = 0, *timeShown = (long long *)calloc(n, sizeof(long long)); for (int i = 0; i < roadsSize; i++) for (int j = 0; j < 2; j++) timeShown[roads[i][j]]++; @@ -18,12 +26,13 @@ long long maximumImportance(int n, int **roads, int roadsSize, } int main() { - int roads1[][2] = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}}, + int r1[][2] = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}}, roadsColSize1[] = {6}; - int roads2[][2] = {{0, 3}, {2, 4}, {1, 3}}, roadsColSize2[] = {3}; - printf("%llu\n", maximumImportance(5, roads1, 6, roadsColSize1)); // expect: - // 43 - printf("%llu\n", maximumImportance(5, roads1, 3, roadsColSize1)); // expect: - // 20 - return 0; + int r2[][2] = {{0, 3}, {2, 4}, {1, 3}}, roadsColSize2[] = {3}; + printf("%llu\n", + maximumImportance(5, (int **)r1, 6, roadsColSize1)); // expect: + // 43 + printf("%llu\n", + maximumImportance(5, (int **)r1, 3, roadsColSize1)); // expect: + // 20 } diff --git a/max_total_importance_road.cpp b/max_total_importance_road.cpp new file mode 100644 index 0000000..327edb2 --- /dev/null +++ b/max_total_importance_road.cpp @@ -0,0 +1,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(int) r1 = {{0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 4}}; + vvd(int) 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 +} diff --git a/max_total_importance_road.py b/max_total_importance_road.py new file mode 100644 index 0000000..ae52cfe --- /dev/null +++ b/max_total_importance_road.py @@ -0,0 +1,37 @@ +# 2285. Maximum Total Importance of Roads + +""" +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(object): + def maximumImportance(self, n, roads): + """ + :type n: int + :type roads: List[List[int]] + :rtype: int + """ + sum, dp = 0, [0] * n + for i, j in roads: + dp[i] += 1 + dp[j] += 1 + roads.sort() + for i in range(len(roads)): + sum += dp[i] * (i + 1) + return sum + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maximumImportance( + n=5, roads=[[0, 1], [1, 2], [2, 3], [0, 2], [1, 3], [2, 4]] + ) + ) + print(obj.maximumImportance(n=5, roads=[[0, 3], [2, 4], [1, 3]])) |