Watch 10 video solutions for Reschedule Meetings for Maximum Free Time I, a medium level problem involving Array, Greedy, Sliding Window. This walkthrough by codestorywithMIK has 14,043 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer eventTime denoting the duration of an event, where the event occurs from time t = 0 to time t = eventTime.
You are also given two integer arrays startTime and endTime, each of length n. These represent the start and end time of n non-overlapping meetings, where the ith meeting occurs during the time [startTime[i], endTime[i]].
You can reschedule at most k meetings by moving their start time while maintaining the same duration, to maximize the longest continuous period of free time during the event.
The relative order of all the meetings should stay the same and they should remain non-overlapping.
Return the maximum amount of free time possible after rearranging the meetings.
Note that the meetings can not be rescheduled to a time outside the event.
Example 1:
Input: eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
Output: 2
Explanation:
Reschedule the meeting at [1, 2] to [2, 3], leaving no meetings during the time [0, 2].
Example 2:
Input: eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
Output: 6
Explanation:
Reschedule the meeting at [2, 4] to [1, 3], leaving no meetings during the time [3, 9].
Example 3:
Input: eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
Output: 0
Explanation:
There is no time during the event not occupied by meetings.
Constraints:
1 <= eventTime <= 109n == startTime.length == endTime.length2 <= n <= 1051 <= k <= n0 <= startTime[i] < endTime[i] <= eventTimeendTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].Problem Overview: You are given a schedule of non‑overlapping meetings inside a fixed event duration. You may reschedule up to k meetings while keeping their durations the same. The goal is to maximize the length of a single continuous block of free time.
Approach 1: Sliding Window on Meetings (O(n) time, O(n) space)
The key observation: if you move k meetings elsewhere, the gap created spans from the end of the meeting before the window to the start of the meeting after the window. Iterate through the meetings and consider every group of k consecutive meetings as candidates to reschedule. For a window starting at i, the left boundary is the end time of meeting i-1 (or 0 if it’s the first meeting). The right boundary is the start time of meeting i+k (or eventTime if the window reaches the end). The free time becomes rightStart - leftEnd. A sliding window efficiently checks all such groups in linear time.
This works because removing a contiguous block of meetings merges the surrounding gaps into one large free interval. The approach naturally fits problems involving ordered intervals and window scanning, which often appear with array processing.
Approach 2: Sliding Window with Space Optimization (O(n) time, O(1) space)
You can compute the same window boundaries without storing extra structures. Track indices directly and compute boundaries using the original startTime and endTime arrays. For each index i, determine the previous meeting’s end and the next meeting’s start using simple conditional checks. The maximum difference across all windows is the answer.
This version reduces memory usage while preserving the same logic. The algorithm remains linear because each meeting index is visited once and each window shift performs constant work. The method also reflects a typical greedy perspective: remove the block of meetings that unlocks the largest possible continuous gap.
Recommended for interviews: The sliding window solution is what interviewers expect. It shows you recognize that removing k consecutive meetings merges surrounding gaps and can be evaluated with a linear scan. A brute‑force approach that tries all combinations would be exponential or O(n^2), which demonstrates baseline reasoning but not the optimization skills usually required for medium interval problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window on Meetings | O(n) | O(n) | Clear implementation when auxiliary arrays or precomputed gaps are acceptable |
| Sliding Window (Space Optimized) | O(n) | O(1) | Best for interviews and production when memory usage should stay constant |