{"id":5124,"date":"2019-04-28T22:19:52","date_gmt":"2019-04-29T05:19:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5124"},"modified":"2019-04-28T22:33:38","modified_gmt":"2019-04-29T05:33:38","slug":"leetcode-853-car-fleet","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-853-car-fleet\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 853. Car Fleet"},"content":{"rendered":"\n

N<\/code> cars are going to the same destination along a one lane road.  The destination is target<\/code> miles away.<\/p>\n\n\n\n

Each car i<\/code> has a constant speed speed[i]<\/code> (in miles per hour), and initial position position[i]<\/code> miles towards the target along the road.<\/p>\n\n\n\n

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.<\/p>\n\n\n\n

The distance between these two cars is ignored – they are assumed to have the same position.<\/p>\n\n\n\n

A car fleet<\/em> is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.<\/p>\n\n\n\n

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.<\/p>\n\n\n\n


How many car fleets will arrive at the destination?<\/p>\n\n\n\n

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

Input: <\/strong>target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]\nOutput: <\/strong>3\nExplanation<\/strong>:\nThe cars starting at 10 and 8 become a fleet, meeting each other at 12.\nThe car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.\nThe cars starting at 5 and 3 become a fleet, meeting each other at 6.\nNote that no other cars meet these fleets before the destination, so the answer is 3.\n<\/pre>\n\n\n\n

Note:<\/strong><\/p>\n\n\n\n
  1. 0 <= N <= 10 ^ 4<\/code><\/li>
  2. 0 < target <= 10 ^ 6<\/code><\/li>
  3. 0 < speed[i] <= 10 ^ 6<\/code><\/li>
  4. 0 <= position[i] < target<\/code><\/li>
  5. All initial positions are different.<\/li><\/ol>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    1. Compute the time when each car can reach target.<\/li>
    2.  Sort cars by position DESC <\/li><\/ol>\n\n\n\n
      Answer will be number slow cars in the time array.<\/p>\n\n\n\n
      \nEx 1: \ntarget = 12\np = [10,8,0,5,3] \nv = [2,4,1,1,3]\n\n\np     t\n10    1  <- slow -- ^\n 8    1             |\n 5    7  <- slow -- ^\n 3    3             |\n 0   12  <- slow -- ^\n\nEx 2\ntarget = 10\np = [5, 4, 3, 2, 1]\nv = [1, 2, 3, 4, 5]\n\np     t\n5     5  <- slow -- ^\n4     3             |\n3     2.33          |\n2     2             |\n1     1.8           |\n\n<\/pre>\n\n\n\n
      Time complexity: O(nlogn)
      Space complexity: O(n)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua, running time: 52 ms \/ 10.9 MB\nclass Solution {\npublic:\n  int carFleet(int target, vector& position, vector& speed) {\n    vector> cars(position.size());\n    for (int i = 0; i < position.size(); ++i)\n      cars[i] = {position[i], static_cast(target - position[i]) \/ speed[i]};\n    sort(rbegin(cars), rend(cars));    \n    int ans{0};\n    float max_t{0};\n    for (const auto& [p, t] : cars)       \n      if (t > max_t) {\n        max_t = t;\n        ++ans;\n      }    \n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
      Python3<\/h2>\n
      \n\n
      \nclass Solution:\n  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n    cars = sorted([(p, (target - p) \/ s) for p, s in zip(position, speed)], \n                  key=lambda x: -x[0])\n    ans, max_t = 0, 0    \n    for p, t in cars:\n      if t > max_t:\n        ans += 1\n        max_t = t\n    return ans\n        \n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      N cars are going to the same destination along a one lane road.  The destination is target miles away. Each car i has a constant speed speed[i] (in miles per hour), and…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,23,472],"class_list":["post-5124","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-sort","tag-sweepline","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5124","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=5124"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5124\/revisions"}],"predecessor-version":[{"id":5128,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5124\/revisions\/5128"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5124"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5124"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5124"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}