Minimum Skips to Arrive at Meeting On Time

Hard
1516.

Minimum Skips to Arrive at Meeting On Time

Minimum Skips to Arrive at Meeting On Time is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

You have hoursBefore hours to reach a meeting, and the way there is n roads driven in order; road i is dist[i] kilometres long. You always drive at speed km/h.

After each road you must rest until the next whole hour before starting the next road. For example, if a road ends 1.4 hours after you set off, you wait until hour 2; if it ends exactly at hour 2, there is no wait. No rest is needed after the last road, since you have arrived.

To save time you may skip some rests and start the next road immediately. Return the minimum number of skips needed to arrive at the meeting on time (arriving exactly at hour hoursBefore counts), or -1 if that is impossible.

Example 1

Input
dist = [3,1,2], speed = 4, hoursBefore = 2
Output
1
Explanation
Without skips you arrive at 2.5 hours. Skip the first rest: 0.75 + 0.25 = 1.0 hours, no wait, then 1.0 + 0.5 = 1.5 hours.

Example 2

Input
dist = [2,3,1], speed = 3, hoursBefore = 2
Output
2
Explanation
The roads need exactly 2 hours of driving, so no waiting at all is affordable.

Example 3

Input
dist = [5,5], speed = 2, hoursBefore = 4
Output
-1
Explanation
Driving alone takes 5 hours.

Constraints

  • n == dist.length
  • 1 <= n <= 1000
  • 1 <= dist[i] <= 10^5
  • 1 <= speed <= 10^6
  • 1 <= hoursBefore <= 10^7
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} dist
 * @param {number} speed
 * @param {number} hoursBefore
 * @return {number}
 */
var minSkips = function(dist, speed, hoursBefore) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Skips to Arrive at Meeting On Time — Solution

Minimum Skips to Arrive at Meeting On Time solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Skips to Arrive at Meeting On Time is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have hoursBefore hours to reach a meeting, and the way there is n roads driven in order; road i is dist[i] kilometres long. You always drive at speed km/h.

After each road you must rest until the next whole hour before starting the next road. For example, if a road ends 1.4 hours after you set off, you wait until hour 2; if it ends exactly at hour 2, there is no wait. No rest is needed after the last road, since you have arrived.

To save time you may skip some rests and start the next road immediately. Return the minimum number of skips needed to arrive at the meeting on time (arriving exactly at hour hoursBefore counts), or -1 if that is impossible.

Example 1

Input: dist = [3,1,2], speed = 4, hoursBefore = 2
Output: 1
Explanation: Without skips you arrive at 2.5 hours. Skip the first rest: 0.75 + 0.25 = 1.0 hours, no wait, then 1.0 + 0.5 = 1.5 hours.

Example 2

Input: dist = [2,3,1], speed = 3, hoursBefore = 2
Output: 2
Explanation: The roads need exactly 2 hours of driving, so no waiting at all is affordable.

Example 3

Input: dist = [5,5], speed = 2, hoursBefore = 4
Output: -1
Explanation: Driving alone takes 5 hours.

Constraints

  • n == dist.length
  • 1 <= n <= 1000
  • 1 <= dist[i] <= 10^5
  • 1 <= speed <= 10^6
  • 1 <= hoursBefore <= 10^7

Hints for Minimum Skips to Arrive at Meeting On Time

  1. Hint 1

    Greedy choices of which rests to skip go wrong; think about the best arrival time after i roads having used exactly j skips.

  2. Hint 2

    Fractions of hours invite floating-point errors. Measure time in units of 1 / speed hours instead: road i then takes exactly dist[i] units, and 'the next whole hour' is the next multiple of speed.

  3. Hint 3

    dp[j] = the earliest time (in those units) after the current road with j skips. Resting rounds t + dist[i] up to a multiple of speed; skipping keeps t + dist[i] and uses one more skip. Answer: the smallest j with dp[j] + dist[n-1] <= hoursBefore · speed.

How to solve Minimum Skips to Arrive at Meeting On Time

With a fixed number of skips, finishing a prefix of roads earlier is never worse, so dp[i][j] = the earliest finishing time of the first i roads with j skips is an optimal-substructure state. Scaling time by speed turns every quantity into an integer and the rest rule into 'round up to a multiple of speed'.

Approach

  1. Work in units of 1 / speed hours: road i takes dist[i] units and the deadline is hoursBefore · speed units (use 64-bit integers).
  2. dp[0] = 0, all other entries infinite.
  3. For every road i except the last, build next: from each finite dp[j], let t = dp[j] + dist[i]; resting gives next[j] = min(next[j], ceil(t / speed) · speed); skipping gives next[j+1] = min(next[j+1], t).
  4. Finally, return the smallest j with dp[j] + dist[n-1] <= hoursBefore · speed, or -1 if there is none.

Why it works

Among plans that cover the first i roads with exactly j skips, the one that finishes earliest dominates: rounding up to the next hour is monotone, so starting the remaining roads earlier can only make every later time earlier or equal. So keeping the minimum per (i, j) loses nothing, and the two transitions cover the only decision after each road. Integer units make the rounding exact — no floating-point comparison can misjudge a time that lands exactly on an hour.

Complexity

  • Time — O(n^2)
  • Space — O(n)

Pitfalls

  • Floating-point times such as 1/3 + 2/3 can come out as 0.999… or 1.000…1 and wrongly add or skip an hour of waiting — use integer units.
  • No rest after the last road: add the final road without rounding.
  • hoursBefore · speed can reach 10^13 — compute it in 64 bits.

Reference solution

Python

from typing import List

def minSkips(dist: List[int], speed: int, hoursBefore: int) -> int:
    n = len(dist)
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0
    for i in range(n - 1):
        nd = [INF] * (n + 1)
        for j in range(i + 1):
            if dp[j] == INF:
                continue
            t = dp[j] + dist[i]
            rested = (t + speed - 1) // speed * speed
            if rested < nd[j]:
                nd[j] = rested
            if t < nd[j + 1]:
                nd[j + 1] = t
        dp = nd
    limit = hoursBefore * speed
    for j in range(n):
        if dp[j] != INF and dp[j] + dist[n - 1] <= limit:
            return j
    return -1

Java

public static int minSkips(int[] dist, int speed, int hoursBefore) {
    int n = dist.length;
    final long INF = Long.MAX_VALUE / 4;
    long[] dp = new long[n + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        long[] nd = new long[n + 1];
        Arrays.fill(nd, INF);
        for (int j = 0; j <= i; j++) {
            if (dp[j] == INF) continue;
            long t = dp[j] + dist[i];
            long rested = (t + speed - 1) / speed * speed;
            if (rested < nd[j]) nd[j] = rested;
            if (t < nd[j + 1]) nd[j + 1] = t;
        }
        dp = nd;
    }
    long limit = (long) hoursBefore * speed;
    for (int j = 0; j < n; j++) {
        if (dp[j] != INF && dp[j] + dist[n - 1] <= limit) return j;
    }
    return -1;
}

C++

int minSkips(vector<int>& dist, int speed, int hoursBefore) {
    int n = dist.size();
    const long long INF = LLONG_MAX / 4;
    vector<long long> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        vector<long long> nd(n + 1, INF);
        for (int j = 0; j <= i; j++) {
            if (dp[j] == INF) continue;
            long long t = dp[j] + dist[i];
            long long rested = (t + speed - 1) / speed * speed;
            nd[j] = min(nd[j], rested);
            nd[j + 1] = min(nd[j + 1], t);
        }
        dp = nd;
    }
    long long limit = (long long)hoursBefore * speed;
    for (int j = 0; j < n; j++) {
        if (dp[j] != INF && dp[j] + dist[n - 1] <= limit) return j;
    }
    return -1;
}

JavaScript

var minSkips = function(dist, speed, hoursBefore) {
    var n = dist.length, INF = Infinity;
    var dp = new Array(n + 1).fill(INF);
    dp[0] = 0;
    for (var i = 0; i < n - 1; i++) {
        var nd = new Array(n + 1).fill(INF);
        for (var j = 0; j <= i; j++) {
            if (dp[j] === INF) continue;
            var t = dp[j] + dist[i];
            var rested = Math.floor((t + speed - 1) / speed) * speed;
            if (rested < nd[j]) nd[j] = rested;
            if (t < nd[j + 1]) nd[j + 1] = t;
        }
        dp = nd;
    }
    var limit = hoursBefore * speed;
    for (var j = 0; j < n; j++) {
        if (dp[j] !== INF && dp[j] + dist[n - 1] <= limit) return j;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming