Leetcode 1870. Minimum Speed to Arrive on Time

1870. Minimum Speed to Arrive on Time

アプローチ

• 二分探索を活用

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int start = 1;
        int end = 1000000000;
        int result = -1;

        while (start <= end) {
            int midSpeed = start + (end - start) / 2;
            double keisan = 0.0;
            for (int i = 0; i < dist.length; i++) {
                keisan = Math.ceil(keisan);
                // 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. という条件があり、切り上げ処理が必要

                keisan += Double.valueOf(dist[i]) / Double.valueOf(midSpeed);
                // keisan = Math.ceil(keisan);
                // 合算したあと、切り上げ処理を行うと、最後の計算後に再度切り上げするようになるので合算の先に行う
            }
            
            if (keisan <= hour) {
                // 距離、時間、速度の計算公式で求めている時間より計算結果がつい盛ったら
                // 最後の時間を減らす
                end = midSpeed - 1;
                result = midSpeed;
            } else {
                start = midSpeed + 1;
            }
        }
        return result;
    }
}