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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Skips to Arrive at Meeting On Time

Difficulty: Hard

Problem Description

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 i-th 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.

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.

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

Key Insights

  • Calculate the time taken for each road segment based on distance and speed.
  • Use dynamic programming to track the minimum time needed to reach each road with a varying number of skips.
  • Determine if it's possible to reach the destination within the given time frame by comparing total travel time against hoursBefore.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution involves using dynamic programming to track the minimum time required to reach each road segment with a specific number of skips. We maintain a DP table where dp[i][j] represents the minimum time to reach road i with j skips. We iterate through each road and update the DP table based on whether we skip the rest or not. The final answer is found by checking the last road segment for all possible skips.

Code Solutions

def minSkips(dist, speed, hoursBefore):
    n = len(dist)
    dp = [[float('inf')] * (n + 1) for _ in range(n)]
    
    for j in range(n + 1):
        dp[0][j] = dist[0] / speed + j  # time to travel first road
    
    for i in range(1, n):
        for j in range(i + 1):  # j can go from 0 to i
            travel_time = dist[i] / speed
            
            # If we do not skip the rest
            if j < i:
                dp[i][j] = dp[i - 1][j] + travel_time
                if dp[i][j] > int(dp[i][j]):  # if we finish in fraction of hour
                    dp[i][j] = int(dp[i][j]) + 1
            
            # If we skip the rest
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + travel_time)
    
    for j in range(n + 1):
        if dp[n - 1][j] <= hoursBefore:
            return j
    
    return -1
← Back to All Questions