{"id":9446,"date":"2022-01-30T16:28:09","date_gmt":"2022-01-31T00:28:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9446"},"modified":"2022-01-30T16:34:51","modified_gmt":"2022-01-31T00:34:51","slug":"leetcode-2141-maximum-running-time-of-n-computers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2141-maximum-running-time-of-n-computers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2141. Maximum Running Time of N Computers"},"content":{"rendered":"\n

You have n<\/code> computers. You are given the integer n<\/code> and a 0-indexed<\/strong> integer array batteries<\/code> where the ith<\/sup><\/code> battery can run<\/strong> a computer for batteries[i]<\/code> minutes. You are interested in running all<\/strong> n<\/code> computers simultaneously<\/strong> using the given batteries.<\/p>\n\n\n\n

Initially, you can insert at most one battery<\/strong> into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times<\/strong>. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.<\/p>\n\n\n\n

Note that the batteries cannot be recharged.<\/p>\n\n\n\n

Return the maximum<\/strong> number of minutes you can run all the <\/em>n<\/code> computers simultaneously.<\/em><\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 2, batteries = [3,3,3]\nOutput:<\/strong> 4\nExplanation:<\/strong> \nInitially, insert battery 0 into the first computer and battery 1 into the second computer.\nAfter two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.\nAt the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.\nBy the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.\nWe can run the two computers simultaneously for at most 4 minutes, so we return 4.\n\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 2, batteries = [1,1,1,1]\nOutput:<\/strong> 2\nExplanation:<\/strong> \nInitially, insert battery 0 into the first computer and battery 2 into the second computer. \nAfter one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. \nAfter another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.\nWe can run the two computers simultaneously for at most 2 minutes, so we return 2.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= batteries.length <= 105<\/sup><\/code><\/li>
  • 1 <= batteries[i] <= 109<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Binary Search<\/strong><\/h2>\n\n\n\n
    Find the smallest L that we can not run, ans = L – 1.<\/p>\n\n\n\n
    For a guessing m, we check the total battery powers T = sum(min(m, batteries[i])), if T >= m * n, it means there is a way (doesn’t need to figure out how) to run n computers for m minutes by fully unitize those batteries.<\/p>\n\n\n\n
    Proof: If T >= m*n holds, there are two cases:<\/p>\n\n\n\n
    1. There are only n batteries, can not swap, but each of them has power >= m.<\/li>
    2. At least one of the batteries have power less than m, but there are more than n batteries and total power is sufficient, we can swap them with others.<\/li><\/ol>\n\n\n\n
      Time complexity: O(Slogn) where S = sum(batteries)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  long long maxRunTime(int n, vector& batteries) {\n    long long l = 0;\n    long long r = accumulate(begin(batteries), end(batteries), 0LL) + 1;\n    while (l < r) {\n      long long m = l + (r - l) \/ 2;\n      long long t = 0;\n      for (long long b : batteries)\n        t += min(m, b);\n      if (m * n > t) \/\/ smallest m that does not fit.\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l - 1; \/\/ greatest m that fits.\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries. Initially, you can insert at…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,749,217],"class_list":["post-9446","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-gready","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9446","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=9446"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9446\/revisions"}],"predecessor-version":[{"id":9451,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9446\/revisions\/9451"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}