Minimum Skips To Arrive At Meeting On Time - Leetcode Solution

Problem description: You are given an array of integers arr, representing the starting time of each person to arrive at a meeting. The meeting starts at time 0 and you need to arrive at the meeting on time. You are allowed to skip any number of people in order to arrive on time, however, if you skip a person, you need to wait for the next person to arrive before you can continue walking towards the meeting. Find the minimum number of people that you need to skip in order to arrive at the meeting on time.

Solution approach: One way to solve this problem is to use dynamic programming. We can define dp[i][j] as the minimum number of people that we need to skip in order to arrive at the meeting on time, if we have already skipped j people and have reached the i-th person in the array. The base case is when i = 0, meaning we have already arrived at the meeting on time, hence dp[0][j] = 0 for all j.

Then, for each i > 0, we need to consider two cases:

1. We skip the i-th person: If we skip the i-th person, we need to add 1 to the number of people we have skipped so far, hence dp[i][j] = dp[i-1][j-1].
2. We wait for the i-th person: If we wait for the i-th person, we don't need to skip anyone else, hence dp[i][j] = dp[i-1][j] + arr[i].

Finally, we need to choose the minimum between the two cases above, i.e., dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + arr[i]), for i > 0 and 1 <= j <= i.

The answer to the problem is the minimum j such that dp[n][j] <= j * k, where n is the length of the arr and k is the time needed to arrive at the meeting.

Code implementation:

class Solution {
public:
    int minSkips(vector<int>& arr, int k) {
        int n = arr.size();
        vector<vector<long long>> dp(n+1, vector<long long>(n+1, INT_MAX));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = min(dp[i-1][j-1] + arr[i-1], dp[i-1][j] + k - (arr[i-1] % k));
            }
        }
        for (int j = 0; j <= n; j++) {
            if (dp[n][j] <= (long long) k * j) {
                return j;
            }
        }
        return -1;
    }
};

The time complexity of the algorithm is O(n^2) and the space complexity is O(n^2), where n is the length of the arr.

1