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.

&nbsp;
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.


Example 2:

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3:
- The first train ride takes 1/3 = 0.33333 hours.
- 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.
- 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.
- You will arrive at the 2.66667 hour mark.


Example 3:

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.


&nbsp;
Constraints:


	n == dist.length
	1 &lt;= n &lt;= 105
	1 &lt;= dist[i] &lt;= 105
	1 &lt;= hour &lt;= 109
	There will be at most two digits after the decimal point in hour.


class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        # the speed upper is either the longest train ride: max(dist),
        # or the last train ride divide by 0.01: ceil(dist[-1] / 0.01).
        # notice: "hour will have at most two digits after the decimal point"
        upper = max(max(dist), ceil(dist[-1] / 0.01))
        #
        # the function to calcute total time consumed
        total = lambda speed: sum(map(lambda x: ceil(x / speed), dist[:-1])) + (dist[-1] / speed)
        # the case of impossible to arrive office on time
        if total(upper) > hour:
            return -1
        #
        # binary search: find the mimimal among "all" feasible answers
        left, right = 1, upper
        while left < right:
            mid = left + (right - left) // 2
            if total(mid) > hour:
                left = mid + 1 # should be larger
            else:
                right = mid # should explore a smaller one
        return right
class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int left = 1;
        int right = (int) 1e8;

        while (left < right) {
            int middle = (left + right) / 2;
            if (arriveOnTime(dist, hour, middle))
                right = middle;
            else left = middle + 1;
        }

        return right == (int) 1e8 ? -1 : right;
    }

    private boolean arriveOnTime(int[] dist, double hour, int speed) {
        int time = 0;
        for (int i = 0; i < dist.length - 1; i++) {
            time += Math.ceil((double) dist[i] / speed);
        }
        return time + (double) dist[dist.length - 1] / speed <= hour;
    }
}
class Solution
{
    bool canReachInTime(const vector<int>& dist, const double hour, int speed)
    {
        double time = 0;
        for (int i = 0; i < dist.size() - 1; ++i)
            time += ((dist[i] + speed - 1) / speed);

        time += ((double)dist.back()) / speed;
        return time <= hour;
    }

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

        int lo = 1, hi = 1e7, mi;
        while (lo < hi)
        {
            mi = (lo + hi) / 2;
            if (canReachInTime(dist, hour, mi))
                hi = mi;
            else
                lo = mi + 1;
        }

        return hi;
    }
};
var minSpeedOnTime = function(dist, hour) {
    let left=1,right=10000000,speed,sum,ans=-1;
    while(left<=right){
        //We need to return the minimum positive integer speed (in kilometers per hour) that all the trains must travel. So speed will always be an integer ranging from 1 to 10000000 as per the question description.
        speed = left + Math.floor((right-left)/2);
        sum=0;
        for(let i=0;i<dist.length-1;i++){
            sum += Math.ceil((dist[i]/speed));
        }
        sum += (dist[dist.length-1]/speed);//For the last train we need not to do Math.ceil
        if(sum<=hour){//sum(time taken is less than the required time, so it can be our answer, but we will keep looking for the another smaller speed until left<=right)
            ans=speed;
            right = speed-1;
        }else{
            left=speed+1;
        }
    }
    return ans;
};
Minimum Speed to Arrive on Time