Minimum Speed to Arrive on Time

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 is simple yet profound: given an array of distances and a time limit, what is the minimum speed you need to maintain to arrive on time?

Imagine you’re late for a meeting, and you have to speed through traffic like a superhero. But wait! You can’t just drive like a maniac; you need to calculate the minimum speed required to avoid being late. This is where our problem comes in.

Code Solution


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

    while (l <= r) {
      final 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(int[] dist, double hour, int speed) {
    double sum = 0;
    for (int i = 0; i < dist.length - 1; ++i)
      sum += Math.ceil((double) dist[i] / speed);
    return sum + (double) dist[dist.length - 1] / speed;
  }
}

Approach Explanation

The approach used in the code is a binary search method to find the minimum speed required to reach the destination on time. The algorithm works as follows:

Initialization: Set the left boundary (l) to 1 (minimum speed) and the right boundary (r) to a large number (1e7).
Binary Search: While l is less than or equal to r, calculate the mid-point speed (m).
Time Calculation: Use the time function to determine if the current speed allows you to arrive on time. If the time exceeds the given hour, increase the speed by adjusting the left boundary. Otherwise, store the current speed as a potential answer and decrease the right boundary.
Return Result: After the loop, return the minimum speed found.

Time and Space Complexity

Time Complexity: O(n log(maxSpeed)), where n is the number of distances and maxSpeed is the upper limit of speed (1e7). The binary search runs in log time, and for each speed, we calculate the time which takes O(n).

Space Complexity: O(1), as we are using a constant amount of space for variables.

Real-World Example

Picture this: You're at a party, and your friends are waiting for you to arrive. You have to travel 100 miles, and you have only 2 hours to get there. You start calculating how fast you need to go. If you drive at 50 mph, you’ll arrive in 2 hours, but if you slow down to 40 mph, you’ll be late! This is the essence of the Minimum Speed to Arrive on Time problem.