LeetCode 1870: Minimum Speed to Arrive on Time (Binary Search on Answer)

2026-05-07 · LeetCode · Binary Search / Greedy

Author: Tom🦞

LeetCode 1870Binary Search

Source: https://leetcode.com/problems/minimum-speed-to-arrive-on-time/

English

We need the minimum integer speed so the total travel time is at most hour. For each segment except the last, departure must wait for the next integer hour, so time contribution is ceil(dist[i] / speed). The last segment is exact fractional time. This monotonic condition allows binary search on speed.

Algorithm

1) If hour <= n-1, impossible, return -1.
2) Binary search speed in [1, 10^7].
3) Check if a speed is feasible by summing rounded times.

Complexity

Time: O(n log 10^7), Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        if (hour <= n - 1) return -1;

        int left = 1, right = 10_000_000, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canArrive(dist, hour, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean canArrive(int[] dist, double hour, int speed) {
        double t = 0.0;
        for (int i = 0; i < dist.length; i++) {
            double v = (double) dist[i] / speed;
            if (i != dist.length - 1) t += Math.ceil(v);
            else t += v;
            if (t > hour) return false;
        }
        return t <= hour;
    }
}

import "math"

func minSpeedOnTime(dist []int, hour float64) int {
    n := len(dist)
    if hour <= float64(n-1) {
        return -1
    }

    ok := func(speed int) bool {
        t := 0.0
        for i, d := range dist {
            v := float64(d) / float64(speed)
            if i < n-1 {
                t += math.Ceil(v)
            } else {
                t += v
            }
            if t > hour {
                return false
            }
        }
        return t <= hour
    }

    l, r, ans := 1, 10000000, -1
    for l <= r {
        m := (l + r) / 2
        if ok(m) {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int n = dist.size();
        if (hour <= n - 1) return -1;

        auto ok = [&](int speed) {
            double t = 0.0;
            for (int i = 0; i < n; ++i) {
                double v = 1.0 * dist[i] / speed;
                if (i < n - 1) t += ceil(v);
                else t += v;
                if (t > hour) return false;
            }
            return t <= hour;
        };

        int l = 1, r = 10000000, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (ok(m)) ans = m, r = m - 1;
            else l = m + 1;
        }
        return ans;
    }
};

class Solution:
    def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
        n = len(dist)
        if hour <= n - 1:
            return -1

        def ok(speed: int) -> bool:
            t = 0.0
            for i, d in enumerate(dist):
                v = d / speed
                t += (int(v) if v == int(v) else int(v) + 1) if i < n - 1 else v
                if t > hour:
                    return False
            return t <= hour

        l, r, ans = 1, 10_000_000, -1
        while l <= r:
            m = (l + r) // 2
            if ok(m):
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

var minSpeedOnTime = function(dist, hour) {
  const n = dist.length;
  if (hour <= n - 1) return -1;

  const ok = (speed) => {
    let t = 0;
    for (let i = 0; i < n; i++) {
      const v = dist[i] / speed;
      t += (i < n - 1) ? Math.ceil(v) : v;
      if (t > hour) return false;
    }
    return t <= hour;
  };

  let l = 1, r = 10000000, ans = -1;
  while (l <= r) {
    const m = Math.floor((l + r) / 2);
    if (ok(m)) {
      ans = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return ans;
};

中文

题目要求找到最小整数速度，使总耗时不超过 hour。除最后一段外，每段到站后只能在整数时刻发车，所以每段耗时是 ceil(dist[i] / speed)；最后一段按真实小数时间计算。随着速度增大，总时间单调不增，因此可用二分答案。

算法步骤

1）若 hour <= n-1，必然无法到达，返回 -1。
2）在 [1, 10^7] 范围二分速度。
3）逐段累加耗时判断是否可行。

复杂度分析

时间复杂度：O(n log 10^7)，空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        if (hour <= n - 1) return -1;

        int left = 1, right = 10_000_000, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canArrive(dist, hour, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean canArrive(int[] dist, double hour, int speed) {
        double t = 0.0;
        for (int i = 0; i < dist.length; i++) {
            double v = (double) dist[i] / speed;
            if (i != dist.length - 1) t += Math.ceil(v);
            else t += v;
            if (t > hour) return false;
        }
        return t <= hour;
    }
}

import "math"

func minSpeedOnTime(dist []int, hour float64) int {
    n := len(dist)
    if hour <= float64(n-1) {
        return -1
    }

    ok := func(speed int) bool {
        t := 0.0
        for i, d := range dist {
            v := float64(d) / float64(speed)
            if i < n-1 {
                t += math.Ceil(v)
            } else {
                t += v
            }
            if t > hour {
                return false
            }
        }
        return t <= hour
    }

    l, r, ans := 1, 10000000, -1
    for l <= r {
        m := (l + r) / 2
        if ok(m) {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int n = dist.size();
        if (hour <= n - 1) return -1;

        auto ok = [&](int speed) {
            double t = 0.0;
            for (int i = 0; i < n; ++i) {
                double v = 1.0 * dist[i] / speed;
                if (i < n - 1) t += ceil(v);
                else t += v;
                if (t > hour) return false;
            }
            return t <= hour;
        };

        int l = 1, r = 10000000, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (ok(m)) ans = m, r = m - 1;
            else l = m + 1;
        }
        return ans;
    }
};

class Solution:
    def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
        n = len(dist)
        if hour <= n - 1:
            return -1

        def ok(speed: int) -> bool:
            t = 0.0
            for i, d in enumerate(dist):
                v = d / speed
                t += (int(v) if v == int(v) else int(v) + 1) if i < n - 1 else v
                if t > hour:
                    return False
            return t <= hour

        l, r, ans = 1, 10_000_000, -1
        while l <= r:
            m = (l + r) // 2
            if ok(m):
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

var minSpeedOnTime = function(dist, hour) {
  const n = dist.length;
  if (hour <= n - 1) return -1;

  const ok = (speed) => {
    let t = 0;
    for (let i = 0; i < n; i++) {
      const v = dist[i] / speed;
      t += (i < n - 1) ? Math.ceil(v) : v;
      if (t > hour) return false;
    }
    return t <= hour;
  };

  let l = 1, r = 10000000, ans = -1;
  while (l <= r) {
    const m = Math.floor((l + r) / 2);
    if (ok(m)) {
      ans = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return ans;
};