Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Greedy · Sliding Window
5 1 [1,3] [2,5]
10 1 [0,2,9] [1,4,10]
5 2 [0,1,2,3,4] [1,2,3,4,5]
meeting-scheduler)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3439: Reschedule Meetings for Maximum Free Time I
class Solution {
public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
int n = endTime.length;
int[] nums = new int[n + 1];
nums[0] = startTime[0];
for (int i = 1; i < n; ++i) {
nums[i] = startTime[i] - endTime[i - 1];
}
nums[n] = eventTime - endTime[n - 1];
int ans = 0, s = 0;
for (int i = 0; i <= n; ++i) {
s += nums[i];
if (i >= k) {
ans = Math.max(ans, s);
s -= nums[i - k];
}
}
return ans;
}
}
// Accepted solution for LeetCode #3439: Reschedule Meetings for Maximum Free Time I
func maxFreeTime(eventTime int, k int, startTime []int, endTime []int) int {
n := len(endTime)
nums := make([]int, n+1)
nums[0] = startTime[0]
for i := 1; i < n; i++ {
nums[i] = startTime[i] - endTime[i-1]
}
nums[n] = eventTime - endTime[n-1]
ans, s := 0, 0
for i := 0; i <= n; i++ {
s += nums[i]
if i >= k {
ans = max(ans, s)
s -= nums[i-k]
}
}
return ans
}
# Accepted solution for LeetCode #3439: Reschedule Meetings for Maximum Free Time I
class Solution:
def maxFreeTime(
self, eventTime: int, k: int, startTime: List[int], endTime: List[int]
) -> int:
nums = [startTime[0]]
for i in range(1, len(endTime)):
nums.append(startTime[i] - endTime[i - 1])
nums.append(eventTime - endTime[-1])
ans = s = 0
for i, x in enumerate(nums):
s += x
if i >= k:
ans = max(ans, s)
s -= nums[i - k]
return ans
// Accepted solution for LeetCode #3439: Reschedule Meetings for Maximum Free Time I
impl Solution {
pub fn max_free_time(event_time: i32, k: i32, start_time: Vec<i32>, end_time: Vec<i32>) -> i32 {
let n = end_time.len();
let mut nums = vec![0; n + 1];
nums[0] = start_time[0];
for i in 1..n {
nums[i] = start_time[i] - end_time[i - 1];
}
nums[n] = event_time - end_time[n - 1];
let mut ans = 0;
let mut s = 0;
for i in 0..=n {
s += nums[i];
if i as i32 >= k {
ans = ans.max(s);
s -= nums[i - k as usize];
}
}
ans
}
}
// Accepted solution for LeetCode #3439: Reschedule Meetings for Maximum Free Time I
function maxFreeTime(eventTime: number, k: number, startTime: number[], endTime: number[]): number {
const n = endTime.length;
const nums: number[] = new Array(n + 1);
nums[0] = startTime[0];
for (let i = 1; i < n; i++) {
nums[i] = startTime[i] - endTime[i - 1];
}
nums[n] = eventTime - endTime[n - 1];
let [ans, s] = [0, 0];
for (let i = 0; i <= n; i++) {
s += nums[i];
if (i >= k) {
ans = Math.max(ans, s);
s -= nums[i - k];
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.