{"id":8484,"date":"2021-08-05T21:35:21","date_gmt":"2021-08-06T04:35:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8484"},"modified":"2021-08-05T21:37:49","modified_gmt":"2021-08-06T04:37:49","slug":"leetcode-1870-minimum-speed-to-arrive-on-time","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1870-minimum-speed-to-arrive-on-time\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1870. Minimum Speed to Arrive on Time"},"content":{"rendered":"\n<p>You are given a floating-point number&nbsp;<code>hour<\/code>, representing the amount of time you have to reach the office. To commute to the office, you must take&nbsp;<code>n<\/code>&nbsp;trains in sequential order. You are also given an integer array&nbsp;<code>dist<\/code>&nbsp;of length&nbsp;<code>n<\/code>, where&nbsp;<code>dist[i]<\/code>&nbsp;describes the distance (in kilometers) of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;train ride.<\/p>\n\n\n\n<p>Each train can only depart at an integer hour, so you may need to wait in between each train ride.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if the&nbsp;<code>1<sup>st<\/sup><\/code>&nbsp;train ride takes&nbsp;<code>1.5<\/code>&nbsp;hours, you must wait for an additional&nbsp;<code>0.5<\/code>&nbsp;hours before you can depart on the&nbsp;<code>2<sup>nd<\/sup><\/code>&nbsp;train ride at the 2 hour mark.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum positive integer<\/strong>&nbsp;speed&nbsp;<strong>(in kilometers per hour)<\/strong>&nbsp;that all the trains must travel at for you to reach the office on time, or&nbsp;<\/em><code>-1<\/code><em>&nbsp;if it is impossible to be on time<\/em>.<\/p>\n\n\n\n<p>Tests are generated such that the answer will not exceed&nbsp;<code>10<sup>7<\/sup><\/code>&nbsp;and&nbsp;<code>hour<\/code>&nbsp;will have&nbsp;<strong>at most two digits after the decimal point<\/strong>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> dist = [1,3,2], hour = 6\n<strong>Output:<\/strong> 1\n<strong>Explanation: <\/strong>At speed 1:\n- The first train ride takes 1\/1 = 1 hour.\n- Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3\/1 = 3 hours.\n- Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2\/1 = 2 hours.\n- You will arrive at exactly the 6 hour mark.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> dist = [1,3,2], hour = 2.7\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>At speed 3:\n- The first train ride takes 1\/3 = 0.33333 hours.\n- Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3\/3 = 1 hour.\n- Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2\/3 = 0.66667 hours.\n- You will arrive at the 2.66667 hour mark.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> dist = [1,3,2], hour = 1.9\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> It is impossible because the earliest the third train can depart is at the 2 hour mark.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == dist.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= dist[i] &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= hour &lt;= 10<sup>9<\/sup><\/code><\/li><li>There will be at most two digits after the decimal point in&nbsp;<code>hour<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<p>l = speed<sub>min<\/sub>=1<br>r = speed<sub>max<\/sub>+1 = 1e7 + 1<\/p>\n\n\n\n<p>Find the min valid speed m such that t(m) &lt;= hour.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minSpeedOnTime(vector<int>& dist, double hour) {\n    constexpr int kMax = 1e7 + 1;\n    const int n = dist.size();    \n    int l = 1;\n    int r = kMax;    \n    while (l < r) {\n      int m = l + (r - l) \/ 2;\n      int t = 0;\n      for (int i = 0; i < n - 1; ++i)\n        t += (dist[i] + m - 1) \/ m;\n      if (t + dist.back() * 1.0 \/ m <= hour)\n        r = m;\n      else\n        l = m + 1;      \n    }\n    return l == kMax ? -1 : l;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a floating-point number&nbsp;hour, representing the amount of time you have to reach the office. To commute to the office, you must take&nbsp;n&nbsp;trains&#8230;<\/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,714,177],"class_list":["post-8484","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-ceil","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8484","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=8484"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8484\/revisions"}],"predecessor-version":[{"id":8486,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8484\/revisions\/8486"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}