Reschedule Meetings for Maximum Free Time I

I realized immediately that this question only cares about the difference between endTime[i] and startTime[i+1], and that the value of k just limits the number of endTime[i] and startTime[i+1] we can concatenate.

To make the rest of the description easier on my end, I will denote the difference between endTime[i] and startTime[i+1] as break[i].

Therefore, we can simply run a sliding window algorithm, where we remove the leftmost break value from our sum and add the next break value to our sum. Initially, I used a queue to track this easily, however you can do this with O(1) space by just doing addition to subtract off the front of the sliding window.

Some edge cases to consider was that the difference between startTime[0] and 0 and the difference between eventTime and endTime.back(). I accounted for:

1. the first by adding startTime[0]-0 to sum initially, and incrementing the sliding window counter initially.
2. the second by simply push_backing eventTime to the end of startTime

code

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int i = 0;
        int sum = startTime[0];
        startTime.push_back(eventTime);
        while (i+1 <= k) {
            sum += startTime[i+1] - endTime[i];
            ++i;
        }
        int ans = sum;

        if (i < startTime.size()-1) {
            sum -= startTime[0];
            sum += startTime[i+1]-endTime[i];
            ans = max(ans, sum);
            ++i;
        }

        for (; i < startTime.size()-1; ++i) {
            sum -= startTime[i-k] - endTime[i-k-1];
            sum += startTime[i+1] - endTime[i];
            ans = max(ans, sum);
            }
        return ans;
    }
};

complexity

• Time: O(n) where n is the size of both startTime and endTime
• Space: O(1)

time taken

• 9 minutes and 53 seconds