Minimum Speed to Arrive on Time – C++ Solution

Problem Description

Ah, the classic dilemma of arriving on time! You know, that moment when you realize you have to travel a certain distance, and you start calculating how fast you need to go to avoid the wrath of your boss or the disappointment of your friends. The problem at hand is called Minimum Speed to Arrive on Time.

Imagine you’re late for a meeting, and you have to cover a distance of dist miles. You have a deadline, or as we like to call it, a “time limit” (let’s say hour hours). The catch? You can’t just teleport there; you need to drive at a certain speed. The question is: what’s the minimum speed you need to maintain to arrive on time?

In simpler terms, if you’re driving like a tortoise, you might as well just stay home. But if you speed up like a cheetah, you might just make it!

Code Solution


class Solution {
 public:
  int minSpeedOnTime(vector& dist, double hour) {
    int ans = -1;
    int l = 1;
    int r = 1e7;

    while (l <= r) {
      const int m = (l + r) / 2;
      if (time(dist, hour, m) > hour) {
        l = m + 1;
      } else {
        ans = m;
        r = m - 1;
      }
    }

    return ans;
  }

 private:
  double time(const vector& dist, double hour, int speed) {
    double sum = 0;
    for (int i = 0; i < dist.size() - 1; ++i)
      sum += ceil((double)dist[i] / speed);
    return sum + (double)dist.back() / speed;
  }
};

Approach

The approach used in this solution is a binary search method. We start with a speed range from 1 to 10 million. We calculate the time it would take to travel the distance at the midpoint speed. If the time exceeds the given hour, we increase the speed (move to the right in our search). If it’s within the limit, we record that speed as a potential answer and try to find a smaller speed (move to the left). This continues until we find the minimum speed that allows us to arrive on time.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log m)
Space Complexity	O(1)

Real-World Example

Let’s say you’re trying to catch a flight. You have to travel 300 miles to the airport, and your flight leaves in 3 hours. If you’re driving at a leisurely pace of 50 mph, you’ll arrive in 6 hours. Oops! Looks like you need to step on the gas! The minimum speed you need to maintain to make it on time is calculated using the above code.