We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Skips to Arrive at Meeting On Time

Number: 2013

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of road distances, a constant travel speed, and a deadline (in hours), determine the minimum number of skips needed such that you can reach the destination on time. Normally, after finishing each road (except the last), you must wait until the next integer hour before continuing, but you are allowed to skip some of these waiting periods. If it is impossible to meet the deadline even after skipping all wait periods, return -1.

Key Insights

  • The travel time on each road is calculated as (distance / speed).
  • After each road (except the final one), if you do not skip, you must round up the elapsed time to the next integer.
  • Skipping the rest allows you to keep the fractional travel time without waiting.
  • The problem can be solved using dynamic programming where dp[i][k] represents the minimal time to reach the end of the i-th road having skipped exactly k rests.
  • There are two choices for each road: skip the waiting period (if allowed) or do not skip (thus rounding up the time).
  • The answer is the smallest k such that the total time after the last road is less than or equal to hoursBefore.

Space and Time Complexity

Time Complexity: O(n^2) – where n is the number of roads, since we iterate through each road and potential number of skips. Space Complexity: O(n^2) – storing a DP table with dimensions [n+1] x [n+1].

Solution

We use a dynamic programming approach. Define dp[i][j] as the minimum time required to finish the first i roads with exactly j skips used. For each road:

  1. Compute the travel time for the current road as dist[i-1] / speed.
  2. If the road is not the last, for the non-skipped case, add the travel time then round up (using ceil) to simulate the waiting period.
  3. For the skip case, simply add the travel time (no rounding).
  4. Continue updating the dp table.
  5. Finally, check for the smallest number of skips for which the total time on finishing the last road is within hoursBefore. Data structures used include a 2D DP array. The algorithmic trick uses DP state transitions by considering both skipping and not skipping at each road, keeping track of minimal times.

Code Solutions

# Python solution

import math

def minSkips(dist, speed, hoursBefore):
    n = len(dist)
    # Using a large number for initialization, maximum possible time is set to a very high value.
    dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # No roads traveled, time = 0
    
    for i in range(1, n + 1):
        travel_time = dist[i - 1] / speed
        for j in range(0, i + 1):
            # Case 1: Not skipping the rest after this road (only if it's not the last road)
            if j <= i - 1:
                # Only add waiting time if not last road by rounding up the time. 
                if i < n:
                    dp[i][j] = min(dp[i][j], math.ceil(dp[i - 1][j] + travel_time))
                else:
                    # Last road, no need to wait.
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + travel_time)
            # Case 2: Skipping the waiting period (allowed if j > 0)
            if j > 0:
                # Add travel time without rounding up (skipping rest)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + travel_time)
                    
    for skips in range(n + 1):
        if dp[n][skips] <= hoursBefore:
            return skips
    return -1

# Example Usage:
print(minSkips([1,3,2], 4, 2))   # Output: 1
print(minSkips([7,3,5,5], 2, 10))  # Output: 2
print(minSkips([7,3,5,5], 1, 10))  # Output: -1
← Back to All Questions