{"id":9512,"date":"2022-02-27T05:03:25","date_gmt":"2022-02-27T13:03:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9512"},"modified":"2022-02-27T05:11:49","modified_gmt":"2022-02-27T13:11:49","slug":"leetcode-2187-minimum-time-to-complete-trips","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2187-minimum-time-to-complete-trips\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2187. Minimum Time to Complete Trips"},"content":{"rendered":"\n

You are given an array time<\/code> where time[i]<\/code> denotes the time taken by the ith<\/sup><\/code> bus to complete one trip<\/strong>.<\/p>\n\n\n\n

Each bus can make multiple trips successively<\/strong>; that is, the next trip can start immediately after<\/strong> completing the current trip. Also, each bus operates independently<\/strong>; that is, the trips of one bus do not influence the trips of any other bus.<\/p>\n\n\n\n

You are also given an integer totalTrips<\/code>, which denotes the number of trips all buses should make in total<\/strong>. Return the minimum time<\/strong> required for all buses to complete at least<\/strong> <\/em>totalTrips<\/code> trips<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> time = [1,2,3], totalTrips = 5\nOutput:<\/strong> 3\nExplanation:<\/strong>\n- At time t = 1, the number of trips completed by each bus are [1,0,0]. \n  The total number of trips completed is 1 + 0 + 0 = 1.\n- At time t = 2, the number of trips completed by each bus are [2,1,0]. \n  The total number of trips completed is 2 + 1 + 0 = 3.\n- At time t = 3, the number of trips completed by each bus are [3,1,1]. \n  The total number of trips completed is 3 + 1 + 1 = 5.\nSo the minimum time needed for all buses to complete at least 5 trips is 3.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> time = [2], totalTrips = 1\nOutput:<\/strong> 2\nExplanation:<\/strong>\nThere is only one bus, and it will complete its first trip at t = 2.\nSo the minimum time needed to complete 1 trip is 2.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= time.length <= 105<\/sup><\/code><\/li>
  • 1 <= time[i], totalTrips <= 107<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Binary Search<\/strong><\/h2>\n\n\n\n
    Find the smallest t s.t. trips >= totalTrips.<\/p>\n\n\n\n
    Time complexity: O(nlogm), where m ~= 1e15
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  long long minimumTime(vector& time, int totalTrips) {\n    long long l = 1;\n    long long r = 1e15;\n    while (l < r) {\n      long long m = l + (r - l) \/ 2;\n      long long trips = 0;\n      for (int t : time) {        \n        trips += m \/ t;\n        if (trips >= totalTrips) break;\n      }\n      if (trips >= totalTrips)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip. Each bus can make multiple trips successively; that is, the next trip can…<\/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,177],"class_list":["post-9512","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9512","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=9512"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9512\/revisions"}],"predecessor-version":[{"id":9515,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9512\/revisions\/9515"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}