Minimum Skips to Arrive at Meeting On Time LeetCode solution in Java

1
class Solution {
2
  public int minSkips(int[] dist, int speed, int hoursBefore) {
3
    int N = dist.length, INF = (int) 1e9;
4
    int[] dp = new int[N];
5
    Arrays.fill(dp, INF);
6
    dp[0] = 0; // before we start, we have a time of 0 for 0 cost
7
    for (int i = 0; i < N; i++) {
8
      for (int j = i;
9
          j >= 0;
10
          j--) { // j (cost) is at most i (num of element-1) so we start from there.
11
        dp[j] = Math.min(j == 0 ? INF : dp[j - 1] + dist[i], ceil(dp[j], speed) + dist[i]);
12
      }
13
    }
14
    for (int i = 0;
15
        i < N;
16
        i++) { // find the min cost (i) such that the min time is no greater than hoursBefore
17
      if (ceil(dp[i], speed) / speed <= hoursBefore) {
18
        return i;
19
      }
20
    }
21
    return -1;
22
  }
23

24
  private int ceil(int n, int s) {
25
    return n + (s - n % s) % s;
26
  }
27
}