# Reschedule Meetings for Maximum Free Time II **Difficulty:** MEDIUM [External](https://leetcode.com/problems/reschedule-meetings-for-maximum-free-time-ii) Canonical: https://scaleengineer.com/dsa/problems/reschedule-meetings-for-maximum-free-time-ii **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration) **Data structures:** Array --- ## Problem You are given an integer `eventTime` denoting the duration of an event. You are also given two integer arrays `startTime` and `endTime`, each of length `n`. These represent the start and end times of `n` **non-overlapping** meetings that occur during the event between time `t = 0` and time `t = eventTime`, where the `ith` meeting occurs during the time `[startTime[i], endTime[i]].` You can reschedule **at most** one meeting by moving its start time while maintaining the **same duration**, such that the meetings remain non-overlapping, to **maximize** the **longest** _continuous period of free time_ during the event. 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 and they should remain non-overlapping. **Note:** _In this version_, it is **valid** for the relative ordering of the meetings to change after rescheduling one meeting. **Example 1:** **Input:** eventTime = 5, startTime = \[1,3\], endTime = \[2,5\] **Output:** 2 **Explanation:** ![](https://assets.glich.co/dsa/reschedule-meetings-for-maximum-free-time-ii/image0.png) Reschedule the meeting at `[1, 2]` to `[2, 3]`, leaving no meetings during the time `[0, 2]`. **Example 2:** **Input:** eventTime = 10, startTime = \[0,7,9\], endTime = \[1,8,10\] **Output:** 7 **Explanation:** ![](https://assets.glich.co/dsa/reschedule-meetings-for-maximum-free-time-ii/image1.png) Reschedule the meeting at `[0, 1]` to `[8, 9]`, leaving no meetings during the time `[0, 7]`. **Example 3:** **Input:** eventTime = 10, startTime = \[0,3,7,9\], endTime = \[1,4,8,10\] **Output:** 6 **Explanation:** **![](https://assets.glich.co/dsa/reschedule-meetings-for-maximum-free-time-ii/image2.png)** Reschedule the meeting at `[3, 4]` to `[8, 9]`, leaving no meetings during the time `[1, 7]`. **Example 4:** **Input:** eventTime = 5, 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 <= 109` * `n == startTime.length == endTime.length` * `2 <= n <= 105` * `0 <= startTime[i] < endTime[i] <= eventTime` * `endTime[i] <= startTime[i + 1]` where `i` lies in the range `[0, n - 2]`. # Approaches ## Brute Force by Simulating Each Move This approach systematically explores all possibilities by trying to reschedule each meeting one by one. For each meeting chosen to be moved, it recalculates the entire schedule's free time and determines the optimal placement for that single meeting to maximize the longest continuous free period. While straightforward and easy to conceptualize, its inefficiency makes it impractical for large inputs. **Time:** O(N^2) - The outer loop runs `N` times. Inside, creating the list of `n-1` meetings and calculating free slots takes `O(N)` time. · **Space:** O(N) - to store the temporary list of free slots for each iteration. **Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs. **Cons:** The time complexity of `O(N^2)` is too slow for the given constraints (`N` up to `10^5`) and will result in a 'Time Limit Exceeded' error on most platforms. ### Explanation The core idea is to iterate through every meeting and treat it as the candidate for rescheduling. When we select a meeting `i` to move, we temporarily remove it from the schedule. This leaves `n-1` meetings, which define `n` free time slots. We then analyze these `n` slots to find the best place to re-insert the meeting `i`. The goal is to maximize the longest continuous free time. Let the duration of meeting `i` be `d_i`. After removing it, we find the lengths of all `n` free slots. Let the largest be `L_max` and the second largest be `L_second_max`. To maximize the final free time, we should try to preserve the largest existing free slot if possible. If we can place meeting `i` into any free slot other than the largest one (which is possible if `d_i` is less than or equal to `L_second_max`), the new maximum free time will be `L_max`. If our meeting is too long for any but the largest slot, we are forced to use it, reducing its length. The new maximum free time becomes `max(L_max - d_i, L_second_max)`. We repeat this for every meeting `i` and take the maximum value found across all simulations. ```java class Solution { public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) { int n = startTime.length; // Calculate initial max free time (no move) int initialMaxFree = 0; if (n > 0) { initialMaxFree = startTime[0]; for (int i = 0; i < n - 1; i++) { initialMaxFree = Math.max(initialMaxFree, startTime[i + 1] - endTime[i]); } initialMaxFree = Math.max(initialMaxFree, eventTime - endTime[n - 1]); } else { return eventTime; } int overallMaxFreeTime = initialMaxFree; // Iterate through each meeting to reschedule for (int i = 0; i < n; i++) { int duration = endTime[i] - startTime[i]; // Calculate free slots if meeting i is removed java.util.List freeSlots = new java.util.ArrayList<>(); int lastEnd = 0; for (int j = 0; j < n; j++) { if (i == j) continue; freeSlots.add(startTime[j] - lastEnd); lastEnd = endTime[j]; } freeSlots.add(eventTime - lastEnd); // Find L_max and L_second_max int lMax = 0; int lSecondMax = 0; for (int slot : freeSlots) { if (slot > lMax) { lSecondMax = lMax; lMax = slot; } else if (slot > lSecondMax) { lSecondMax = slot; } } int currentMax = 0; if (duration <= lSecondMax) { currentMax = lMax; } else if (duration <= lMax) { currentMax = Math.max(lMax - duration, lSecondMax); } if (currentMax > 0) { overallMaxFreeTime = Math.max(overallMaxFreeTime, currentMax); } } return overallMaxFreeTime; } } ``` ### Algorithm 1. Calculate the initial maximum free time without rescheduling any meetings. This serves as a baseline answer. 2. Iterate through each meeting `i` from `0` to `n-1`, considering it as the one to be rescheduled. 3. For each meeting `i`: a. Determine its duration, `d_i = endTime[i] - startTime[i]`. b. Simulate the removal of meeting `i`. Construct a new list of `n-1` meetings. c. Calculate the `n` continuous free time intervals based on these `n-1` meetings and the event boundaries `[0, eventTime]`. d. From the list of `n` free interval lengths, find the largest (`L_max`) and the second-largest (`L_second_max`). e. Determine the best possible maximum free time if meeting `i` is moved: i. If the meeting can be placed in a slot that is not the largest (i.e., `d_i <= L_second_max`), the largest slot `L_max` remains untouched. The maximum free time achievable is `L_max`. ii. If the meeting can only fit in the largest slot (i.e., `d_i > L_second_max` but `d_i <= L_max`), it must be placed there. The new maximum free time will be `max(L_max - d_i, L_second_max)`. iii. If the meeting cannot be moved (`d_i > L_max`), no improvement is made for this choice of `i`. f. Update the overall maximum free time with the result calculated for moving meeting `i`. 4. After checking all `n` meetings, the overall maximum is the answer. ## Linear Time Approach with Precomputation The `O(N^2)` approach is too slow because it repeatedly recalculates information. A linear time solution can be achieved by precomputing all necessary values. We can calculate all original free slots, meeting durations, and the potential 'merged' free slots that would be created by removing each meeting. The main challenge is, for each meeting `i` we consider moving, to quickly find the best slot to place it in among the remaining `n-2` original free slots. This can be solved efficiently by using prefix and suffix arrays that store the top two maximum values, allowing for `O(1)` queries. **Time:** O(N) - The precomputation steps take O(N) time, and the final calculation is a single loop through `N` meetings, with O(1) work inside. · **Space:** O(N) - for storing durations, original free slots, merged slots, and prefix/suffix max arrays. **Pros:** Highly efficient with a linear time complexity.; Scales well for large inputs as specified by the constraints. **Cons:** More complex to implement due to multiple precomputation steps and intricate logic.; Requires extra space for several auxiliary arrays. ### Explanation This optimized approach avoids redundant computations through a series of pre-calculation steps. First, we compute three key arrays: - `d`: durations of all `n` meetings. - `f`: lengths of the initial `n+1` free slots. - `S`: lengths of the `n` potential 'merged' slots, where `S[i]` is the length of the free time created by removing meeting `i`. To efficiently find the best placement for a moved meeting, we need to know the largest and second-largest free slots available. The available slots are the original free slots `f_j` excluding the two that were merged. To find the top two of this remaining set in constant time, we precompute `prefix_max2` and `suffix_max2` arrays over the `f` array. `prefix_max2[k]` stores the two largest values in `f[0...k]`, and `suffix_max2[k]` does the same for `f[k...n]`. With these structures, we can iterate through each meeting `i` to be moved. In `O(1)` time, we can retrieve the largest (`M_i`) and second-largest (`M_i_sec`) free slots from the set of slots not adjacent to meeting `i`. Then, we analyze the scenarios: 1. Place meeting `i` (duration `d_i`) into its own merged slot `S_i`. The resulting max free time is `max(S_i - d_i, M_i)`. This is possible if `S_i >= d_i`. 2. Place `d_i` into one of the other slots. If we can use a slot of size `M_i_sec` or smaller, the new max is `max(S_i, M_i)`. If we must use the slot of size `M_i`, the new max is `max(S_i, M_i - d_i, M_i_sec)`. By comparing the outcomes of these scenarios for each `i` and updating a global maximum, we can find the answer in a single pass after precomputation. ```java class Solution { public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) { int n = startTime.length; if (n == 0) return eventTime; int[] d = new int[n]; for (int i = 0; i < n; i++) d[i] = endTime[i] - startTime[i]; long[] f = new long[n + 1]; f[0] = startTime[0]; for (int i = 0; i < n - 1; i++) f[i + 1] = (long)startTime[i + 1] - endTime[i]; f[n] = (long)eventTime - endTime[n - 1]; long[] S = new long[n]; if (n > 1) { S[0] = startTime[1]; for (int i = 1; i < n - 1; i++) S[i] = (long)startTime[i + 1] - endTime[i - 1]; S[n - 1] = (long)eventTime - endTime[n - 2]; } else { S[0] = eventTime; } long[][] prefixMax2 = new long[n + 1][2]; long[][] suffixMax2 = new long[n + 2][2]; for (int i = 0; i <= n; i++) { if (i > 0) { prefixMax2[i][0] = prefixMax2[i - 1][0]; prefixMax2[i][1] = prefixMax2[i - 1][1]; } if (f[i] > prefixMax2[i][0]) { prefixMax2[i][1] = prefixMax2[i][0]; prefixMax2[i][0] = f[i]; } else if (f[i] > prefixMax2[i][1]) { prefixMax2[i][1] = f[i]; } } for (int i = n; i >= 0; i--) { suffixMax2[i][0] = suffixMax2[i + 1][0]; suffixMax2[i][1] = suffixMax2[i + 1][1]; if (f[i] > suffixMax2[i][0]) { suffixMax2[i][1] = suffixMax2[i][0]; suffixMax2[i][0] = f[i]; } else if (f[i] > suffixMax2[i][1]) { suffixMax2[i][1] = f[i]; } } long maxFreeTime = prefixMax2[n][0]; for (int i = 0; i < n; i++) { long duration = d[i]; long mergedLen = S[i]; long[] pMax = (i > 0) ? prefixMax2[i - 1] : new long[]{0, 0}; long[] sMax = (i + 2 <= n + 1) ? suffixMax2[i + 2] : new long[]{0, 0}; long m1 = 0, m2 = 0; long[] candidates = {pMax[0], pMax[1], sMax[0], sMax[1]}; for(long val : candidates) { if (val > m1) { m2 = m1; m1 = val; } else if (val > m2) { m2 = val; } } long currentBestForI = 0; if (mergedLen >= duration) { currentBestForI = Math.max(currentBestForI, Math.max(mergedLen - duration, m1)); } if (m2 >= duration) { currentBestForI = Math.max(currentBestForI, Math.max(mergedLen, m1)); } else if (m1 >= duration) { currentBestForI = Math.max(currentBestForI, Math.max(mergedLen, Math.max(m2, m1 - duration))); } maxFreeTime = Math.max(maxFreeTime, currentBestForI); } return (int) maxFreeTime; } } ``` ### Algorithm 1. **Precomputation (`O(N)`):** a. Calculate `d_i`: the duration of each meeting `i`. b. Calculate `f_j`: the length of the `n+1` original free slots. c. Calculate `S_i`: the length of the large free slot created by removing meeting `i` and merging its adjacent free slots. d. To efficiently query the largest and second-largest free slots among a range, precompute prefix and suffix arrays storing the top two maximums. `prefix_max2[j]` will store the top two values in `f[0...j]`, and `suffix_max2[j]` will store the top two in `f[j...n]`. 2. **Calculation (`O(N)`):** a. Initialize `max_free_time` with the maximum of the original free slots `f_j`. b. Iterate through each meeting `i` from `0` to `n-1`. c. For each `i`, use the precomputed prefix/suffix arrays to find the largest (`M_i`) and second-largest (`M_i_sec`) free slots among those not involved in the merge (i.e., from the set `{f_j | j != i, j != i+1}`). This query takes `O(1)` time. d. Consider all valid placements for meeting `i` (duration `d_i`) and calculate the potential maximum free time: i. **Place in the merged slot `S_i`**: If `S_i >= d_i`, the potential max free time is `max(S_i - d_i, M_i)`. ii. **Place in another slot**: If we can place it in the second-largest available slot (`M_i_sec >= d_i`), the largest slot `M_i` is preserved, and the max free time is `max(S_i, M_i)`. If we can only place it in the largest available slot (`M_i >= d_i`), the max free time is `max(S_i, M_i - d_i, M_i_sec)`. e. Update the overall `max_free_time` with the best result found for meeting `i`. 3. **Return `max_free_time`**. # Solutions ### Python ```python class Solution: def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int: n = len(startTime) res = 0 left_gaps = [0] * n left_gaps[0] = startTime[0] for meet in range(1, n): left_gaps[meet] = max(left_gaps[meet - 1], startTime[meet] - endTime[meet - 1]) right_gaps = [0] * n right_gaps[n - 1] = eventTime - endTime[- 1] for meet in range(n - 2, - 1, - 1): right_gaps[meet] = max(right_gaps[meet + 1], startTime[meet + 1] - endTime[meet]) for meet in range(n): left_gap = (left_gaps[meet] if meet == 0 else startTime[meet] - endTime[meet - 1]) right_gap = (right_gaps[meet] if meet == n - 1 else startTime[meet + 1] - endTime[meet]) interval = 0 if (meet != 0 and left_gaps[meet - 1] >= (endTime[meet] - startTime[meet]) or meet != n - 1 and right_gaps[meet + 1] >= (endTime[meet] - startTime[meet])): interval = endTime[meet] - startTime[meet] res = max(res, left_gap + interval + right_gap) return res ```