DAY 53 - Minimum Speed to Arrive on Time

Hey everyone! Welcome back to another day of problem-solving. It's day 53, and I'm still going strong on my quest for consistency.
Today and we will be solving the daily leetcode problem.

Question:

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the ith train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark.
Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 107 and hour will have at most two digits after the decimal point.

Example 1:

• Input: dist = [1,3,2], hour = 6
• Output: 1
• Explanation: At speed 1:
• The first train ride takes 1/1 = 1 hour.
• Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.
• Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.
• You will arrive at exactly the 6 hour mark.

Algorithm:

• The function minSpeedOnTime takes two inputs: a vector dist containing the distances between consecutive checkpoints and a double hour representing the maximum allowed travel time in hours.
• First, the function calculates the number of checkpoints (n) from the size of the dist vector.
• If the maximum allowed travel time (hour) is less than or equal to the total number of checkpoints minus one (n-1), it means the vehicle cannot reach its destination on time, as the vehicle must spend at least one hour at each checkpoint. In this case, the function returns -1 to indicate that it is not possible to reach the destination on time.
• If the vehicle can reach the destination on time, the function proceeds with a binary search to find the minimum speed required.
• The binary search starts with two pointers: l (left) is initialized to 1 (the minimum possible speed), and r (right) is set to 1e7 (a large value representing the upper bound of speed).
• Inside the binary search loop, the mid pointer is calculated as the average of l and r, representing a candidate speed for the vehicle.
• The variable time is used to store the estimated travel time based on the candidate speed. It is calculated by dividing each distance in dist by the candidate speed (mid) and taking the ceiling of the result. This gives us the time required to travel each distance at the candidate speed. The total travel time is then obtained by summing up all these individual times, including the last distance, which is divided by the candidate speed.
• If the total travel time (time) is less than or equal to the maximum allowed travel time (hour), it means the vehicle can reach its destination on time at the current candidate speed. In this case, we update the right pointer (r) to mid, indicating that we can search for a smaller speed in the left half of the search space.
• If the total travel time (time) exceeds the maximum allowed travel time (hour), it means the vehicle cannot reach its destination on time at the current candidate speed. In this case, we update the left pointer (l) to mid + 1, indicating that we need to search for a larger speed in the right half of the search space.
• The binary search continues until the left pointer (l) is equal to the right pointer (r), at which point the search space has converged to the minimum required speed.
• The function returns the value of the left pointer (l), which represents the minimum speed at which the vehicle should travel to reach its destination on time.

Code:

int minSpeedOnTime(vector<int>& dist, double hour) {
        int n = dist.size();
        if(hour <= n-1) return -1;
        int l=1 , r=1e7;
        while(l<r){
            int mid = l + (r-l)/2;
            double time =0;
            for(int i=0 ; i<n-1 ; i++) time += ceil((double)dist[i]/mid);
            time += (double)dist[n-1]/mid;

            if(time <= hour) r =mid;
            else l = mid+1;
        }
        return l;
    }

Complexity Analysis:

Time: O(log(1e7))
Space: O(1)