Minimum Skips to Arrive at Meeting On Time

Minimum Skips to Arrive at Meeting On Time - Problem

You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the ith road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.

For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly 2 hours, you do not need to wait.

However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.

For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.

Return the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

Input & Output

Example 1 — Basic Case

$ Input: dist = [1,3,4], speed = 1, hoursBefore = 6

› Output: 1

💡 Note: Without skips: 1 hour + rest to 2 + 3 hours + rest to 6 + 4 hours = 10 hours total. With 1 skip: 1 + 3 = 4 hours, rest to 5, then 4 more hours = 9 total > 6. Better: skip after road 2, so 1 + rest to 2 + 3 = 5, skip rest, + 4 = 9. Actually: travel road 1 (1 hr), rest to hour 2, travel road 2 (3 hrs, finish at 5), skip rest, travel road 3 (4 hrs, finish at 9) > 6. Try: skip after road 1: 1 hr + 3 hrs = 4 hrs, rest to 5, + 4 hrs = 9 > 6. Skip after road 2: hour 2 + 3 hrs = 5, + 4 hrs = 9 > 6. Need 1 skip to finish in 6 hours.

Example 2 — Impossible Case

$ Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10

› Output: -1

💡 Note: Even with maximum skips, total time = 7/2 + 3/2 + 5/2 + 5/2 = 10 hours exactly. With rests: 3.5→4 + 1.5→6 + 2.5→9 + 2.5 = 11.5 hours. Need multiple skips but still exceeds time limit.

Example 3 — No Skips Needed

$ Input: dist = [1,1], speed = 1, hoursBefore = 3

› Output: 0

💡 Note: Travel road 1 (1 hour), rest to hour 2, travel road 2 (1 hour), finish at hour 3. Total time = 3 hours ≤ 3, so 0 skips needed.

Constraints

n == dist.length
1 ≤ n ≤ 1000
1 ≤ dist[i] ≤ 10⁵
1 ≤ speed ≤ 10⁶
1 ≤ hoursBefore ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Roads [1,3,4], speed=1, hoursBefore=6

Process

Calculate travel times and decide when to skip rests

Output

Minimum skips needed: 1

Key Takeaway

🎯 Key Insight: Use DP to track minimum time with exactly k skips for optimal solution

Asked in

G Google 15 a Amazon 8 M Microsoft 12

The key insight is to use dynamic programming to track the minimum time needed with exactly k skips. We build a 2D DP table where dp[i][j] represents minimum time for first i roads using j skips. Best approach is 2D Dynamic Programming. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - 2D State	O(n²)	O(n²)	Use DP to track minimum time needed with exactly k skips
Brute Force - Try All Skip Combinations	O(2ⁿ)	O(n)	Try all 2^n combinations of skipping or not skipping each rest

Dynamic Programming - 2D State — Algorithm Steps

Initialize DP table with infinity values
For each road and skip count, try both rest and skip options
Return minimum skips where final time <= hoursBefore

Visualization

Tap to expand

Step-by-Step Walkthrough

DP Table

dp[i][j] = min time for i roads with j skips

Fill Table

For each road, try rest vs skip options

Find Answer

Return minimum j where dp[n][j] ≤ hoursBefore

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>

int solution(int* dist, int n, int speed, int hoursBefore) {
    double dp[1001][1001];
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = DBL_MAX;
        }
    }
    dp[0][0] = 0.0;
    
    for (int i = 0; i < n; i++) {
        double travelTime = (double)dist[i] / speed;
        for (int j = 0; j <= i; j++) {
            if (dp[i][j] == DBL_MAX) continue;
            
            double newTime = dp[i][j] + travelTime;
            
            if (i == n - 1) {
                if (newTime < dp[i + 1][j]) {
                    dp[i + 1][j] = newTime;
                }
            } else {
                double restTime = ceil(newTime);
                if (restTime < dp[i + 1][j]) {
                    dp[i + 1][j] = restTime;
                }
                
                if (j < n && newTime < dp[i + 1][j + 1]) {
                    dp[i + 1][j + 1] = newTime;
                }
            }
        }
    }
    
    for (int j = 0; j <= n; j++) {
        if (dp[n][j] <= hoursBefore + 1e-9) {
            return j;
        }
    }
    
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int dist[1000], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            dist[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int speed, hoursBefore;
    scanf("%d", &speed);
    scanf("%d", &hoursBefore);
    
    int result = solution(dist, n, speed, hoursBefore);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We fill a DP table of size n × n, each cell takes O(1) time

⚠ Quadratic Growth

Space Complexity

O(n²)

DP table stores minimum time for each (road, skip count) pair

⚠ Quadratic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

567 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - 2D State — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler