Reschedule Meetings for the Longest Free Period

### Problem An event runs from time `0` to time `eventTime`. During it, `n` meetings are scheduled in order. Meeting `i` begins at `startTime[i]` and ends at `endTime[i]`; the meetings do not overlap. You may reschedule at most `k` meetings by changing their start times. Every meeting must keep its original duration, remain within the event, and stay in the same relative order as all other meetings. The resulting meetings must still be non-overlapping. Return the greatest possible length of a continuous period with no meeting during the event. You only need to return the length, not a revised schedule. ### C++ Interface ```cpp class Solution { public: int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) { } }; ``` ### Examples **Example 1** ```text Input: eventTime = 12, k = 2, startTime = [1,5,9], endTime = [3,6,11] Output: 6 ``` Move the first two meetings to `[0,2]` and `[2,3]`, and keep the third at `[9,11]`. Durations and order are preserved, and the free period from `3` to `9` has length `6`. No valid rescheduling of at most two meetings yields a longer free period. **Example 2** ```text Input: eventTime = 20, k = 3, startTime = [2,7,15], endTime = [4,9,18] Output: 13 ``` The meeting durations are `2`, `2`, and `3`. Move them to `[0,2]`, `[2,4]`, and `[4,7]`. The remaining period from `7` to `20` has length `13`, equal to all the event's free time. ### Constraints - `1 <= eventTime <= 1000000000`. - `n == startTime.length == endTime.length`. - `2 <= n <= 100000`. - `1 <= k <= n`. - `0 <= startTime[i] < endTime[i] <= eventTime`. - `endTime[i] <= startTime[i + 1]` for every `0 <= i < n - 1`. ### Clarifying Questions - May consecutive meetings touch? Yes. A meeting may end exactly when the next begins; this creates no positive-length free period between them. - May meetings trade places or change duration? No. Both relative order and each duration must remain unchanged. - Must exactly `k` meetings move? No. Moving fewer, including none, is allowed. - Does free time before the first or after the last meeting count? Yes, as long as it lies inside the event. ### What a Strong Answer Covers - Preservation of durations, relative order, non-overlap, and event boundaries. - The distinction between total free time and the longest continuous free period. - Boundary cases with touching meetings, no free time, and permission to move every meeting. - An optimality argument and resource bounds for up to `100000` meetings. ### Follow-up Questions - What answer should be returned when the meetings occupy the entire event without gaps? - If every meeting may be moved, can all the event's free time always form a single continuous period while preserving order? ```hint Join neighboring gaps Moving a consecutive block of meetings can combine the free gaps surrounding and inside that block. Express the original schedule as `n + 1` gap lengths, including the two event boundaries, and consider a window containing `k + 1` gaps. ```