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.
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.
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.
Example 1:
Input: dist = [1,3,2], speed = 4, hoursBefore = 2 Output: 1 Explanation: Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours. You can skip the first rest to arrive in ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 hours. Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.
Example 2:
Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10 Output: 2 Explanation: Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours. You can skip the first and third rest to arrive in ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 hours.
Example 3:
Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10 Output: -1 Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.
Constraints:
n == dist.length1 <= n <= 10001 <= dist[i] <= 1051 <= speed <= 1061 <= hoursBefore <= 107The goal is to calculate the minimum number of skips needed to travel all roads and arrive at the meeting on time. We will use a dynamic programming array dp where dp[i][j] represents the minimum number of skips required to reach road i having already taken j skips. We iterate over each road and simulate the scenarios where you either do or do not skip the waiting time after each.
This solution initializes a 2D dp array. For each road, it considers not skipping and skipping scenarios, updating the dp table accordingly. It calculates the time spent rounding travel time up to the nearest integer when not skipping, and accumulates exact travel time when skipping. The result is extracted by checking which skip count ends up with travel time feasible within hoursBefore.
Java
C#
JavaScript
C
Time Complexity: O(n^2) where n is the number of roads.
Space Complexity: O(n^2) due to the dp table.
An alternative approach would be a greedy strategy mixed with binary search to minimize the skips. However, this is more complex and typically less intuitive than the dynamic programming approach, which explicitly tracks each skip possibility. The feasibility is checked by binary search over possible skips and evaluating if they allow reaching on time.
This C++ solution uses a binary search to find the number of skips needed. It calculates time taken considering the current skip strategy. The search narrows down based on the time it takes compared to allowed hours, attempting different skip counts efficiently.
JavaScript
Time Complexity: O(n log n) due to binary search over skip possibilities multiplied by a linear trip evaluation.
Space Complexity: O(1), since it only uses a few extra variables.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) where n is the number of roads. |
| Greedy Approach | Time Complexity: O(n log n) due to binary search over skip possibilities multiplied by a linear trip evaluation. |
Jump Game - Greedy - Leetcode 55 • NeetCode • 290,098 views views
Watch 9 more video solutions →Practice Minimum Skips to Arrive at Meeting On Time with our built-in code editor and test cases.
Practice on FleetCode