{"id":9827,"date":"2022-09-17T13:04:24","date_gmt":"2022-09-17T20:04:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9827"},"modified":"2022-09-17T13:06:12","modified_gmt":"2022-09-17T20:06:12","slug":"leetcode-2410-maximum-matching-of-players-with-trainers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-2410-maximum-matching-of-players-with-trainers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2410.\u00a0Maximum Matching of Players With Trainers"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array players<\/code>, where players[i]<\/code> represents the ability<\/strong> of the ith<\/sup><\/code> player. You are also given a 0-indexed<\/strong> integer array trainers<\/code>, where trainers[j]<\/code> represents the training capacity <\/strong>of the jth<\/sup><\/code> trainer.<\/p>\n\n\n\n

The ith<\/sup><\/code> player can match<\/strong> with the jth<\/sup><\/code> trainer if the player’s ability is less than or equal to<\/strong> the trainer’s training capacity. Additionally, the ith<\/sup><\/code> player can be matched with at most one trainer, and the jth<\/sup><\/code> trainer can be matched with at most one player.<\/p>\n\n\n\n

Return the maximum<\/strong> number of matchings between <\/em>players<\/code> and <\/em>trainers<\/code> that satisfy these conditions.<\/em><\/p>\n\n\n\n

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

Input:<\/strong> players = [4,7,9], trainers = [8,2,5,8]\nOutput:<\/strong> 2\nExplanation:<\/strong>\nOne of the ways we can form two matchings is as follows:\n- players[0] can be matched with trainers[0] since 4 <= 8.\n- players[1] can be matched with trainers[3] since 7 <= 8.\nIt can be proven that 2 is the maximum number of matchings that can be formed.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> players = [1,1,1], trainers = [10]\nOutput:<\/strong> 1\nExplanation:<\/strong>\nThe trainer can be matched with any of the 3 players.\nEach player can only be matched with one trainer, so the maximum answer is 1.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= players.length, trainers.length <= 105<\/sup><\/code><\/li>
  • 1 <= players[i], trainers[j] <= 109<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Sort + Two Pointers<\/strong><\/h2>\n\n\n\n
    Sort players and trainers.<\/p>\n\n\n\n
    Loop through players, skip trainers until he\/she can match the current players.<\/p>\n\n\n\n
    Time complexity: O(nlogn + mlogm + n + m)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int matchPlayersAndTrainers(vector& players, vector& trainers) {\n    sort(begin(players), end(players));\n    sort(begin(trainers), end(trainers));\n    const int n = players.size();\n    const int m = trainers.size();\n    int ans = 0;\n    for (int i = 0, j = 0; i < n && j < m; ++i) {\n      while (j < m && players[i] > trainers[j]) ++j;\n      if (j++ == m) break;\n      ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer. The ith player can match with the jth trainer if the player’s ability…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[177,23,175],"class_list":["post-9827","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-medium","tag-sort","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9827","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=9827"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9827\/revisions"}],"predecessor-version":[{"id":9830,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9827\/revisions\/9830"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9827"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9827"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9827"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}