Reschedule Meetings for Maximum Free Time II
MedPrompt
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:
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:
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:
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 <= 109n == startTime.length == endTime.length2 <= n <= 1050 <= startTime[i] < endTime[i] <= eventTimeendTime[i] <= startTime[i + 1]whereilies in the range[0, n - 2].
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Calculate the initial maximum free time without rescheduling any meetings. This serves as a baseline answer.
- Iterate through each meeting
ifrom0ton-1, considering it as the one to be rescheduled. - For each meeting
i: a. Determine its duration,d_i = endTime[i] - startTime[i]. b. Simulate the removal of meetingi. Construct a new list ofn-1meetings. c. Calculate thencontinuous free time intervals based on thesen-1meetings and the event boundaries[0, eventTime]. d. From the list ofnfree interval lengths, find the largest (L_max) and the second-largest (L_second_max). e. Determine the best possible maximum free time if meetingiis 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 slotL_maxremains untouched. The maximum free time achievable isL_max. ii. If the meeting can only fit in the largest slot (i.e.,d_i > L_second_maxbutd_i <= L_max), it must be placed there. The new maximum free time will bemax(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 ofi. f. Update the overall maximum free time with the result calculated for moving meetingi. - After checking all
nmeetings, the overall maximum is the answer.
Walkthrough
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.
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<Integer> 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; }}Complexity
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.
Trade-offs
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 (Nup to10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
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.
Algorithm
-
Precomputation (
O(N)): a. Calculated_i: the duration of each meetingi. b. Calculatef_j: the length of then+1original free slots. c. CalculateS_i: the length of the large free slot created by removing meetingiand 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 inf[0...j], andsuffix_max2[j]will store the top two inf[j...n]. -
Calculation (
O(N)): a. Initializemax_free_timewith the maximum of the original free slotsf_j. b. Iterate through each meetingifrom0ton-1. c. For eachi, 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 takesO(1)time. d. Consider all valid placements for meetingi(durationd_i) and calculate the potential maximum free time: i. Place in the merged slotS_i: IfS_i >= d_i, the potential max free time ismax(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 slotM_iis preserved, and the max free time ismax(S_i, M_i). If we can only place it in the largest available slot (M_i >= d_i), the max free time ismax(S_i, M_i - d_i, M_i_sec). e. Update the overallmax_free_timewith the best result found for meetingi. -
Return
max_free_time.
Walkthrough
This optimized approach avoids redundant computations through a series of pre-calculation steps. First, we compute three key arrays:
d: durations of allnmeetings.f: lengths of the initialn+1free slots.S: lengths of thenpotential 'merged' slots, whereS[i]is the length of the free time created by removing meetingi.
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:
- Place meeting
i(durationd_i) into its own merged slotS_i. The resulting max free time ismax(S_i - d_i, M_i). This is possible ifS_i >= d_i. - Place
d_iinto one of the other slots. If we can use a slot of sizeM_i_secor smaller, the new max ismax(S_i, M_i). If we must use the slot of sizeM_i, the new max ismax(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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 resVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.