1883. Minimum Skips to Arrive at Meeting On Time
Problem Description
You are scheduled to attend a meeting and have a fixed number of hours, hoursBefore, to cover a certain distance through n roads. The lengths of these roads are represented as an integer array dist, where dist[i] is the length of the ith road in kilometers. You are given a consistent speed in km/h, denoted by the variable speed.
There is a constraint imposed on your travel -- after completing each road, you're required to rest until the start of the next whole hour before you commence the next leg of your journey. However, this mandatory rest period is waived for the final road as you've already arrived at your destination by then.
Interestingly, to help you arrive on time, you are permitted to skip some of these rest periods. Skipping a rest means you don't have to wait for the next whole hour, which might help you align your travel more closely with the hours available.
The core challenge of the problem is determining the minimum number of rest periods you must skip to ensure you arrive at your meeting on time, if at all possible. If there's no way to make it on time, you should return -1.
Intuition
To solve this problem, dynamic programming is an appropriate approach because we can break down the larger problem into smaller subproblems. Each subproblem involves evaluating the minimal time required to reach the end of a certain road with a specific number of skips.
The intuition behind this approach begins with examining every possible scenario where you choose to either wait for the rest period or skip it after each road. We aim to find the strategy that takes the least amount of time to arrive at the meeting on time while skipping the fewest rest periods.
We maintain an array f, where f[i][j] represents the minimum time to reach the end of the ith road with j skips. The algorithm iterates through each road and each possible number of skips, updating the time calculation to reflect whether we wait or skip after each road.
By initializing f[i][j] with an infinitely large number, we ensure that any actual calculated time will be considered in our comparisons. The iterative process compares the current minimum time f[i][j] with the time achieved by either waiting or skipping the rest period, updating as needed to hold the least time.
With all the subproblems solved, we look for the minimum number of skips needed that still allows us to arrive within hoursBefore. We iterate through the possible number of skips and return the smallest number for which the corresponding time does not exceed hoursBefore. If all scenarios exceed the time limit, we return -1, signaling it's impossible to attend the meeting on time.
The provided solution code represents this approach and calculates the minimum skips required accurately using dynamic programming.
Learn more about Dynamic Programming patterns.
Which two pointer techniques do you use to check if a string is a palindrome?
Solution Approach
The solution utilizes dynamic programming, which involves breaking down the problem into smaller, manageable subproblems and then building up to the solution.
Data Structures:
- A 2D list
fof size(n + 1) x (n + 1)is initialized withinf(representing infinity). This array will store the minimum time needed to reach each road with a given number of skips.
Algorithms and Patterns:
-
Initialization: Since Python lists start at index 0 but roads start at 1, we set
f[0][0]to 0 to denote that at the beginning (before traveling any road), no time has passed. -
Dynamic Programming Iteration:
- The outer loop iterates through each road (denoted by
i), starting from 1, since we consider 0 as the starting point before traveling any road. - The inner loop iterates through every possible number of skips (
j) that could be applied up to the current roadi.
- The outer loop iterates through each road (denoted by
-
State Transition:
- Inside the inner loop, the algorithm considers two scenarios to find the minimum time to complete road
iwithjskips:- Waiting: The algorithm calculates the time if we wait for the next integer hour mark after road
i-1. This is done by addingx / speed(time to travel the current road) tof[i - 1][j](minimum time to reach the previous road with the same number of skips) and applyingceilto round up to the next hour. An epsilonepsis subtracted before applying theceilfunction to handle floating point precision issues. - Skipping: The time is directly added without the ceiling for the case where we skip the rest period after road
i-1. This is only applicable ifjis non-zero, i.e., we have skipped at least once.
- Waiting: The algorithm calculates the time if we wait for the next integer hour mark after road
- Inside the inner loop, the algorithm considers two scenarios to find the minimum time to complete road
-
Comparing and Updating States:
- The algorithm compares the outcomes of waiting and skipping, updating
f[i][j]with the minimum value.
- The algorithm compares the outcomes of waiting and skipping, updating
-
Finding the Result:
- After we've filled in the
farray with the minimum traveling times for all possible skips for each road, the algorithm looks for the smallest number of skips that would still allow us to arrive withinhoursBefore. - This is done by iterating over the possible number of skips for the final road (
f[n][j]wherejranges from0ton) and checking if that time is less than or equal tohoursBefore. A small epsilonepsis added to the time limit to handle floating point precision issues. - If such a
jis found, it's returned as the minimum number of skips required. If all possible skips result in times greater thanhoursBefore, the function returns-1.
- After we've filled in the
By the end of the iteration, the solution will have considered every possible way to allocate the skips to minimize the travel time and determined whether it is possible to arrive on time.
Mathematical Formulas:
- The
ceilfunction is used to account for the need to round up to the next integer hour when waiting after each road, and subtraction of an epsilon is used to correct for any floating point errors that could incorrectly round down when right on the hour mark.
The algorithm's complexity is bounded by the number of roads n and the number of possible skips, which can also be at most n. Hence, we have a time complexity of O(n^2), which is generally acceptable for the road lengths and number of hours before the meeting typically encountered in this type of problem.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Example Walkthrough
To illustrate the solution approach, let's take a small example. Assume we need to cover a distance through 3 roads with lengths given by the array dist = [5, 3, 6], where hoursBefore = 6 hours and our consistent speed is speed = 1 km/h.
Let's create an array f of size (n + 1) x (n + 1) filled with inf to represent the minimum time taken with a corresponding number of skips. The f array would be a 4x4 array in this case, considering n = 3.
We first initialize f[0][0] = 0. This denotes that we're at the starting point and haven't spent any time or skips yet.
The possible states as we iterate through our array f:
1f[0][0] = 0
Moving on to the first road of 5 km:
- Without skipping, we'll spend
ceil(5 / 1) = 5hours, sof[1][0] = 5. - Skipping is not an option since it's the first road.
1f[0][0] = 0 2f[1][0] = 5
Next, the second road of 3 km:
- Without skipping, we'll spend
ceil((5 + 3) / 1) = 8hours in total (5from the first road, and3for this road), sof[2][0] = 8. - With one skip (assuming we skipped after finishing the first road), we would spend
5 (from the first road without waiting) + 3 (second road)hours, sof[2][1] = 8.
1f[0][0] = 0 2f[1][0] = 5 3f[2][0] = 8 4f[2][1] = 8
Finally, the third road of 6 km:
- Without skipping, we're now at
ceil((8 + 6) / 1) = 14hours, but since we can't reach our destination on time without skipping, this attempt is infeasible, so we skip consideringf[3][0]. - With one skip carried over and skipping after the second road, we would spend
5 + 3 + 6 = 14hours, which is again infeasible, sof[3][1]doesn't need to be considered. - With two skips, assuming we skipped after the first and second roads, we would spend
5 + 3 + 6 = 14hours. Since we can skip the rest on the last road,f[3][2] = 14.
1f[0][0] = 0 2f[1][0] = 5 3f[2][0] = 8 (infeasible as exceeds `hoursBefore`) 4f[2][1] = 8 (infeasible as exceeds `hoursBefore`) 5f[3][0] = x 6f[3][1] = x 7f[3][2] = 14
Now, we must consider all options for the number of skips (up to the number of roads n=3). Ideally, we would look for f[n][j] where j ranges from 0 to n (3 in this case) such that f[n][j] <= hoursBefore (6).
When evaluating f[3][2], we can see the value is 14 which exceeds hoursBefore. Thus, none of our options meet the requirement, and we conclude that it is impossible to arrive on time. We return -1.
Solution Implementation
1from math import ceil
2
3class Solution:
4 def minSkips(self, distances: List[int], speed: int, hours_before: int) -> int:
5 # Length of the distances array
6 num_of_sections = len(distances)
7
8 # Initialize a DP table with infinity to store number of skips for reaching certain points
9 dp = [[float('inf')] * (num_of_sections + 1) for _ in range(num_of_sections + 1)]
10
11 # At the beginning, zero skips are made and the total time is also zero
12 dp[0][0] = 0
13
14 # A very small epsilon value to avoid floating-point precision issues
15 epsilon = 1e-8
16
17 # Iterate through each section of the distances
18 for i, distance in enumerate(distances, 1):
19 # For each section, calculate the minimum number of skips required to reach it
20 for skips in range(i + 1):
21 if skips < i:
22 # Option 1: Do not skip this section but might need to skip a future section
23 # Ceil is used to round up to the nearest integer to enforce a rest period
24 dp[i][skips] = min(dp[i][skips], ceil(dp[i - 1][skips] + distance / speed - epsilon))
25 if skips:
26 # Option 2: Skip this section and therefore no rest needed (no ceil)
27 # Can only skip if skips > 0, hence we check it
28 dp[i][skips] = min(dp[i][skips], dp[i - 1][skips - 1] + distance / speed)
29
30 # Check each possible number of skips to see if it fits within the hours_before limit
31 for skips in range(num_of_sections + 1):
32 if dp[num_of_sections][skips] <= hours_before + epsilon:
33 return skips
34
35 # If none fit within the hours_before limit, return -1
36 return -1
371class Solution {
2 public int minSkips(int[] distances, int speed, int hoursBefore) {
3 int numSegments = distances.length;
4 double[][] dp = new double[numSegments + 1][numSegments + 1];
5
6 // Initialize the dp array with a high value
7 for (int i = 0; i <= numSegments; i++) {
8 Arrays.fill(dp[i], 1e20);
9 }
10
11 // Base case: no distance covered without any skips
12 dp[0][0] = 0;
13
14 // Small value to avoid precision issues
15 double eps = 1e-8;
16
17 // Populate the dp array
18 for (int i = 1; i <= numSegments; ++i) {
19 for (int j = 0; j <= i; ++j) {
20 // If not taking the maximum number of skips (which would be the segment index)
21 if (j < i) {
22 dp[i][j] = Math.min(
23 dp[i][j],
24 Math.ceil(dp[i - 1][j] - eps) + (double) distances[i - 1] / speed
25 );
26 }
27 // If taking one less skip
28 if (j > 0) {
29 dp[i][j] = Math.min(
30 dp[i][j],
31 dp[i - 1][j - 1] + (double) distances[i - 1] / speed
32 );
33 }
34 }
35 }
36
37 // Determine the minimum number of skips needed to reach the target within hoursBefore
38 for (int j = 0; j <= numSegments; ++j) {
39 if (dp[numSegments][j] <= hoursBefore + eps) {
40 return j; // Found the minimum skips required
41 }
42 }
43
44 return -1; // It's not possible to reach on time with given constraints
45 }
46}
471class Solution {
2public:
3 int minSkips(vector<int>& distances, int speed, int hoursBefore) {
4 // Number of different distances that we need to travel.
5 int numDistances = distances.size();
6
7 // 'dp' will store the minimum time required to reach a certain point with a given number of skips.
8 // Initialize all values to a very high number, interpreted as 'infinity'.
9 vector<vector<double>> dp(numDistances + 1, vector<double>(numDistances + 1, 1e20));
10
11 // Base case: the time to reach the starting point with 0 skips is 0.
12 dp[0][0] = 0;
13
14 // A small epsilon is used to perform accurate floating-point comparisons later on.
15 double eps = 1e-8;
16
17 // Iterate over each segment of the journey.
18 for (int i = 1; i <= numDistances; ++i) {
19 // Iterate over the possible number of skips.
20 for (int j = 0; j <= i; ++j) {
21 // If we are not skipping the current segment.
22 if (j < i) {
23 dp[i][j] = min(dp[i][j], ceil(dp[i - 1][j] + static_cast<double>(distances[i - 1]) / speed - eps));
24 }
25
26 // If we decide to skip a resting time period.
27 if (j > 0) {
28 dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + static_cast<double>(distances[i - 1]) / speed);
29 }
30 }
31 }
32
33 // Look for the smallest number of skips needed to arrive before or exactly at the prescribed time.
34 for (int j = 0; j <= numDistances; ++j) {
35 if (dp[numDistances][j] <= hoursBefore + eps) {
36 return j; // The minimum number of skips required.
37 }
38 }
39
40 // If it is not possible to arrive on time, return -1.
41 return -1;
42 }
43};
441function minSkips(distances: number[], speed: number, hoursBefore: number): number {
2 // Number of road segments
3 const numSegments = distances.length;
4
5 // Create a 2D array to record the minimum time needed to skip certain number of rests
6 const minTime = Array.from({ length: numSegments + 1 },
7 () => Array.from({ length: numSegments + 1 },
8 () => Infinity));
9
10 // Base case: starting with no distance and no skips, so time is 0
11 minTime[0][0] = 0;
12
13 // Small epsilon value to avoid precision issues with floating point numbers
14 const eps = 1e-8;
15
16 // Iterate through each segment
17 for (let i = 1; i <= numSegments; ++i) {
18 // Calculate the minimum time required with available number of skips
19 for (let j = 0; j <= i; ++j) {
20 // If we do not skip the current rest, use ceil to round to the next integer if necessary
21 if (j < i) {
22 minTime[i][j] = Math.min(minTime[i][j],
23 Math.ceil(minTime[i - 1][j] + distances[i - 1] / speed - eps));
24 }
25
26 // If we can skip, use the exact value (no need to round)
27 if (j) {
28 minTime[i][j] = Math.min(minTime[i][j],
29 minTime[i - 1][j - 1] + distances[i - 1] / speed);
30 }
31 }
32 }
33
34 // Check the minimum number of skips needed to reach within hoursBefore
35 for (let j = 0; j <= numSegments; ++j) {
36 if (minTime[numSegments][j] <= hoursBefore + eps) {
37 return j; // Returns the minimum number of skips needed
38 }
39 }
40
41 // If impossible to reach within hoursBefore, return -1
42 return -1;
43}
44Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Time and Space Complexity
The time complexity of the provided code is O(n^3), where n is the length of the dist array. This is because there are three nested loops: the outermost loop iterating through each element in dist, and two inner loops, where one loop iterates through j from 0 to i+1, and the other considers two possible scenarios for each j (either skipping or not skipping). Each operation inside the innermost loop is O(1), but since the loops are nested, the total time complexity scales cubically.
The space complexity of the code is O(n^2) because of the 2D list f that has dimensions n+1 by n+1. This list stores the minimum time required to reach each point with a given number of skips. Since it needs to hold a value for every combination of distances and skips, the space required grows quadratically with the number of distances.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.