Problem Number

3439

Problem Title

Reschedule Meetings for Maximum Free Time I

LeetCode Link

https://leetcode.com/problems/reschedule-meetings-for-maximum-free-time-i/

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

Compute gaps:
The first gap is the time from 0 to the start of the first event.
The last gap is the time from the end of the last event to eventTime.
For all intermediate gaps, calculate startTime[i] - endTime[i-1].

Sliding window to find maximum sum:
Use two pointers l (left) and r (right) to maintain a window of size k.
Keep a running sum of the gaps in the current window.
As the window moves forward, update the sum by adding the new gap and removing the leftmost gap.

Track the maximum sum seen so far.
Return the result:

After processing all windows, the maximum sum represents the largest total free time for k consecutive gaps.

Intuition

We are asked to find the maximum total free time across k consecutive gaps between events.
The key idea is to first compute all gaps between consecutive events (including the gap before the first event and after the last event). Once we have these gaps, the problem reduces to finding the maximum sum of any k consecutive gaps, which can be efficiently done using a sliding window.

Solution in C++

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<int> temp(n + 1, 0);
        temp[0] = startTime[0] - 0;
        temp[n] = eventTime - endTime[n - 1];
        for (int i = 1; i < n; i++) {
            temp[i] = startTime[i] - endTime[i - 1];
        }
        int l = 0, r = 0, tempsum = 0, maxsum = 0;
        while (r < temp.size()) {
            tempsum += temp[r];
            if ((r - l) == k) {
                maxsum = max(maxsum, tempsum);
                tempsum -= temp[l];
                l++;
            }
            r++;
        }
        return maxsum;
    }
};