{"id":7531,"date":"2020-10-18T11:32:52","date_gmt":"2020-10-18T18:32:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7531"},"modified":"2020-10-18T11:33:47","modified_gmt":"2020-10-18T18:33:47","slug":"leetcode-1626-best-team-with-no-conflicts","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1626-best-team-with-no-conflicts\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1626. Best Team With No Conflicts"},"content":{"rendered":"\n

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum<\/strong> of scores of all the players in the team.<\/p>\n\n\n\n

However, the basketball team is not allowed to have conflicts<\/strong>. A conflict<\/strong> exists if a younger player has a strictly higher<\/strong> score than an older player. A conflict does not<\/strong> occur between players of the same age.<\/p>\n\n\n\n

Given two lists, scores<\/code> and ages<\/code>, where each scores[i]<\/code> and ages[i]<\/code> represents the score and age of the ith<\/sup><\/code> player, respectively, return the highest overall score of all possible basketball teams<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> scores = [1,3,5,10,15], ages = [1,2,3,4,5]\nOutput:<\/strong> 34\nExplanation:<\/strong> You can choose all the players.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> scores = [4,5,6,5], ages = [2,1,2,1]\nOutput:<\/strong> 16\nExplanation:<\/strong> It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> scores = [1,2,3,5], ages = [8,9,10,1]\nOutput:<\/strong> 6\nExplanation:<\/strong> It is best to choose the first 3 players. \n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= scores.length, ages.length <= 1000<\/code><\/li>
  • scores.length == ages.length<\/code><\/li>
  • 1 <= scores[i] <= 106<\/sup><\/code><\/li>
  • 1 <= ages[i] <= 1000<\/code><\/li><\/ul>\n\n\n\n
    Solution: Sort + DP<\/strong><\/h2>\n\n\n\n
    Sort by (age, score) in descending order. For j < i, age[j] >= age[i]<\/p>\n\n\n\n
    dp[i] = max(dp[j] | score[j] >= score[i], j < i) + score[i]<\/p>\n\n\n\n
    Basically, we want to find the player j with best score among [0, i), and make sure score[i] <= score[j] (since age[j] >= age[i]) then we won’t have any conflicts.<\/p>\n\n\n\n
    ans = max(dp)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int bestTeamScore(vector& scores, vector& ages) {\n    const int n = scores.size();\n    vector> players(n);\n    for (int i = 0; i < n; ++i) \n      players[i] = {ages[i], scores[i]};\n    sort(rbegin(players), rend(players));\n    \/\/ dp[i] = max score of the first i players, i must be selected.\n    vector dp(n);\n    for (int i = 0; i < n; ++i) {      \n      for (int j = 0; j < i; ++j)\n        if (players[i].second <= players[j].second)\n          dp[i] = max(dp[i], dp[j]);\n      dp[i] += players[i].second;\n    }\n    return *max_element(begin(dp), end(dp));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177,15],"class_list":["post-7531","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7531","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7531"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7531\/revisions"}],"predecessor-version":[{"id":7533,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7531\/revisions\/7533"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}