Problem Description

You have an event that runs from time t = 0 to time t = eventTime. During this event, there are n scheduled meetings that don't overlap with each other. Each meeting i starts at startTime[i] and ends at endTime[i].

Your task is to reschedule at most k of these meetings to maximize the longest continuous period of free time during the event. When you reschedule a meeting, you can only change its start time while keeping the same duration. The meetings must:

• Remain non-overlapping after rescheduling
• Keep their relative order (if meeting A was before meeting B originally, it must stay before B)
• Stay within the event time bounds (cannot be scheduled outside [0, eventTime])

For example, if you have an event from time 0 to 10, with meetings at [2,4] and [6,8], the free time periods are [0,2], [4,6], and [8,10]. If you can reschedule 1 meeting (k=1), you could move the first meeting to [0,2] to create a longer continuous free period [2,10] of length 8.

The goal is to find the maximum possible length of continuous free time you can create by optimally rescheduling up to k meetings.

Intuition

When we look at this problem, we need to understand what happens when we reschedule meetings. Initially, we have free time gaps between meetings. When we reschedule a meeting, we're essentially moving it to eliminate one gap and extend another gap.

Think about it this way: if we have free time periods like [gap1] meeting1 [gap2] meeting2 [gap3], and we move meeting1 to the left to fill gap1, then gap1 disappears but gap2 grows by the same amount. We've essentially merged gap1 and gap2 into one continuous free period.

The key insight is that when we reschedule k meetings optimally, we can merge up to k+1 consecutive free time gaps. Why k+1? Because:

• Rescheduling 1 meeting merges 2 gaps (the one before and after it)
• Rescheduling 2 adjacent meetings merges 3 gaps
• Rescheduling k adjacent meetings merges k+1 gaps

So the problem transforms into: given all the free time gaps in the event, find the maximum sum of any k+1 consecutive gaps.

We can identify n+1 free time gaps:

• Gap before the first meeting: startTime[0] - 0
• Gaps between consecutive meetings: startTime[i] - endTime[i-1] for each pair
• Gap after the last meeting: eventTime - endTime[-1]

Once we have these gap lengths in an array nums, finding the maximum sum of k+1 consecutive elements is a classic sliding window problem. We maintain a window of size k+1, slide it through the array, and track the maximum sum encountered.

Learn more about Greedy and Sliding Window patterns.

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)

Solution Implementation

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...