Solution Approach

Based on our intuition, we implement the solution using a sliding window approach:

Step 1: Extract Free Time Intervals

First, we build an array nums containing all free time gaps:

• nums[0] = startTime[0] - the gap from event start to first meeting
• For middle gaps: nums[i] = startTime[i] - endTime[i-1] for i from 1 to n-1
• nums[n] = eventTime - endTime[-1] - the gap from last meeting to event end

nums = [startTime[0]] for i in range(1, len(endTime)):  nums.append(startTime[i] - endTime[i - 1]) nums.append(eventTime - endTime[-1])

Step 2: Apply Sliding Window

We need to find the maximum sum of k+1 consecutive elements in nums. We use a sliding window technique:

• Initialize ans = 0 to track the maximum sum and s = 0 for the current window sum
• As we iterate through nums, we add each element to our current sum s
• Once our window reaches size k+1 (when i >= k), we:
  • Update ans with the maximum of current ans and window sum s
  • Remove the leftmost element from the window by subtracting nums[i-k]

ans = s = 0 for i, x in enumerate(nums):  s += x  if i >= k:  ans = max(ans, s)  s -= nums[i - k]

The condition i >= k ensures we have exactly k+1 elements in our window (indices 0 to k inclusive).

Time Complexity: O(n) where n is the number of meetings, as we traverse the array once.

Space Complexity: O(n) for storing the nums array.

This approach efficiently finds the maximum continuous free time by identifying which consecutive gaps to merge through rescheduling meetings.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example Input:

• eventTime = 10
• startTime = [2, 5, 8]
• endTime = [3, 7, 9]
• k = 1 (we can reschedule at most 1 meeting)

Step 1: Identify the free time gaps

First, let's visualize the timeline:

Time: 0 1 2 3 4 5 6 7 8 9 10 Meetings: [M1] [--M2--] [M3] Free: [----] [--] [] []

Now we extract the free time intervals into array nums:

• Gap before first meeting: startTime[0] - 0 = 2 - 0 = 2
• Gap between M1 and M2: startTime[1] - endTime[0] = 5 - 3 = 2
• Gap between M2 and M3: startTime[2] - endTime[1] = 8 - 7 = 1
• Gap after last meeting: eventTime - endTime[2] = 10 - 9 = 1

So nums = [2, 2, 1, 1]

Step 2: Find maximum sum of k+1 consecutive gaps

Since k = 1, we need to find the maximum sum of k+1 = 2 consecutive elements.

Using the sliding window approach:

• Window size = 2
• Initialize: ans = 0, s = 0

Iteration process:

• i = 0: Add nums[0] = 2 to sum → s = 2
  • Window not full yet (i < k), don't update answer
• i = 1: Add nums[1] = 2 to sum → s = 4
  • Window is full (i >= k), update ans = max(0, 4) = 4
  • Remove leftmost element: s = 4 - nums[0] = 4 - 2 = 2
• i = 2: Add nums[2] = 1 to sum → s = 3
  • Window is full, update ans = max(4, 3) = 4
  • Remove leftmost element: s = 3 - nums[1] = 3 - 2 = 1
• i = 3: Add nums[3] = 1 to sum → s = 2
  • Window is full, update ans = max(4, 2) = 4
  • Remove leftmost element: s = 2 - nums[2] = 2 - 1 = 1

Result: Maximum continuous free time = 4

What does this mean? By rescheduling 1 meeting, we can merge 2 consecutive gaps. The best choice is to merge the first two gaps (each of length 2) by moving meeting M1 to start at time 0. This creates one continuous free period from time 2 to time 5, giving us 4 units of free time.

After rescheduling:

Time: 0 1 2 3 4 5 6 7 8 9 10 Meetings: [M1] [--M2--] [M3] Free:  [--------] [] []  (length 4)

Time and Space Complexity

Time Complexity: O(n) where n is the number of meetings (length of startTime and endTime arrays).

The algorithm performs the following operations:

• Building the nums array requires iterating through all meetings once: O(n)
• The sliding window loop iterates through the nums array exactly once: O(n + 1) = O(n) (since nums has n + 1 elements)
• Each operation inside the loop (addition, comparison, subtraction) takes constant time: O(1)

Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n) where n is the number of meetings.

The algorithm uses additional space for:

• The nums array which stores n + 1 elements (free time gaps between meetings plus gaps at the beginning and end): O(n + 1) = O(n)
• A few scalar variables (ans, s, i, x) which take constant space: O(1)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Window Size

The most common mistake is misunderstanding that to merge k meetings, we need k+1 consecutive gaps. Many developers incorrectly use a window size of k instead of k+1.

Incorrect Implementation:

# Wrong: Using window size of k if i >= k - 1: # This checks for k elements, not k+1  max_free_time = max(max_free_time, current_window_sum)  current_window_sum -= free_time_gaps[i - k + 1]

Why it's wrong: When we reschedule k meetings, we're essentially removing k boundaries between free time gaps, which allows us to merge k+1 consecutive gaps into one continuous period.

Correct Implementation:

# Correct: Using window size of k+1 if i >= k: # This ensures we have k+1 elements (indices 0 to k)  max_free_time = max(max_free_time, current_window_sum)  current_window_sum -= free_time_gaps[i - k]

2. Edge Case: k Equals or Exceeds Number of Meetings

When k >= n (where n is the number of meetings), we can reschedule all meetings, potentially creating one continuous free period. The code might fail to handle this properly.

Problem Scenario:

• If k >= len(free_time_gaps) - 1, the sliding window never completes because i never reaches k.

Solution:

def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:  free_time_gaps = []  free_time_gaps.append(startTime[0])  for i in range(1, len(startTime)):  free_time_gaps.append(startTime[i] - endTime[i - 1])  free_time_gaps.append(eventTime - endTime[-1])   # Handle edge case where k allows rescheduling all or more meetings  if k >= len(free_time_gaps) - 1:  return eventTime # All meetings can be moved, entire event is free   max_free_time = 0  current_window_sum = 0   for i, gap_duration in enumerate(free_time_gaps):  current_window_sum += gap_duration  if i >= k:  max_free_time = max(max_free_time, current_window_sum)  current_window_sum -= free_time_gaps[i - k]   return max_free_time

3. Forgetting to Handle Empty Meeting Lists

If there are no meetings (startTime and endTime are empty), the entire event time is already free.

Solution:

def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:  # Handle empty meeting list  if not startTime:  return eventTime   # Rest of the implementation...