Problem Description

You have an event that runs from time t = 0 to time t = eventTime. During this event, there are n non-overlapping meetings scheduled. Each meeting i has a start time startTime[i] and end time endTime[i].

Your task is to find the maximum possible continuous free time period during the event. You can achieve this by rescheduling at most one meeting. When rescheduling a meeting:

• You can change its start time to any valid position
• The meeting must keep the same duration (end time - start time remains unchanged)
• The rescheduled meeting cannot overlap with any other meetings
• The rescheduled meeting must still occur within the event time bounds [0, eventTime]

The goal is to maximize the longest continuous period where no meetings are scheduled.

For example, if you have meetings at [1,3] and [5,7] during an event from 0 to 10, there are three free periods: [0,1], [3,5], and [7,10]. The longest free period is 3 units (from 7 to 10). However, if you reschedule the second meeting to [7,9], you create a longer free period [3,7] of 4 units.

Return the maximum length of continuous free time you can achieve after optimally rescheduling at most one meeting.

Key Points:

• All meetings are initially non-overlapping
• You can reschedule at most one meeting (or none)
• The rescheduled meeting must maintain its original duration
• After rescheduling, meetings can change their relative order (unlike some variants of this problem)
• The rescheduled meeting must remain within the event bounds and not overlap with others

Intuition

To maximize the free time, we need to think about what happens when we move a meeting. Each meeting creates a "barrier" in the timeline, and moving one meeting can potentially merge two separate free periods into one larger continuous free period.

Let's think about meeting i with duration w_i = endTime[i] - startTime[i]. This meeting sits between two boundaries:

• Left boundary l_i: the end of the previous meeting (or 0 if it's the first meeting)
• Right boundary r_i: the start of the next meeting (or eventTime if it's the last meeting)

Without moving any meeting, the free space around meeting i is r_i - l_i - w_i.

Now, what if we move meeting i? The key insight is that we want to "hide" this meeting somewhere else to create a larger free space. Where can we hide it?

1. Move it to an existing free slot on the left: If there's a free period earlier in the timeline that's at least as large as w_i, we can place meeting i there. This would create a new continuous free period of size r_i - l_i.

2. Move it to an existing free slot on the right: Similarly, if there's a free period later that can accommodate meeting i, we get the same benefit: a free period of size r_i - l_i.

This leads us to precompute two important pieces of information:

• pre[i]: the maximum free slot size from the beginning up to position i
• suf[i]: the maximum free slot size from position i to the end

For each meeting, we check three scenarios:

1. Don't move it: free time = r_i - l_i - w_i
2. Move it left (if pre[i-1] >= w_i): free time = r_i - l_i
3. Move it right (if suf[i+1] >= w_i): free time = r_i - l_i

The answer is the maximum free time across all meetings and all valid scenarios. This greedy approach works because we're looking for the single best move that creates the longest continuous free period.

Learn more about Greedy patterns.

Solution Approach

Based on our intuition, we implement the solution using dynamic programming to precompute the maximum free slots, then iterate through each meeting to find the optimal rescheduling.

Step 1: Precompute Maximum Free Slots

First, we build two arrays:

• pre[i]: stores the maximum free slot size from the start up to and including position i
• suf[i]: stores the maximum free slot size from position i to the end

pre[0] = startTime[0]  # Free time before first meeting
suf[n-1] = eventTime - endTime[-1]  # Free time after last meeting

For pre, we iterate forward:

for i in range(1, n):
    pre[i] = max(pre[i-1], startTime[i] - endTime[i-1])

This takes the maximum of the previous maximum and the current gap between meetings.

For suf, we iterate backward:

for i in range(n-2, -1, -1):
    suf[i] = max(suf[i+1], startTime[i+1] - endTime[i])

Step 2: Evaluate Each Meeting

For each meeting i, we determine:

• Left boundary l:
  • l = 0 if i = 0 (first meeting)
  • l = endTime[i-1] otherwise
• Right boundary r:
  • r = eventTime if i = n-1 (last meeting)
  • r = startTime[i+1] otherwise
• Meeting duration: w = endTime[i] - startTime[i]

Step 3: Calculate Maximum Free Time

For each meeting, we consider three scenarios:

1. Don't move the meeting: The free space created is r - l - w

2. Move to a left slot: If i > 0 and pre[i-1] >= w, the meeting can fit in a previous free slot, creating a continuous free period of r - l

3. Move to a right slot: If i < n-1 and suf[i+1] >= w, the meeting can fit in a later free slot, also creating a free period of r - l

The algorithm tracks the maximum free time across all meetings and scenarios:

ans = max(ans, r - l - w)  # Don't move
if i > 0 and pre[i-1] >= w:
    ans = max(ans, r - l)  # Move left
if i+1 < n and suf[i+1] >= w:
    ans = max(ans, r - l)  # Move right

Time Complexity: O(n) where n is the number of meetings. We make three passes through the array.

Space Complexity: O(n) for storing the pre and suf arrays.

Example Walkthrough

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

Example Input:

• eventTime = 10
• startTime = [1, 4, 7]
• endTime = [2, 6, 9]

This gives us meetings at [1,2], [4,6], and [7,9] during an event from time 0 to 10.

Step 1: Build the pre and suf arrays

First, let's identify all free slots:

• Free slot before meeting 0: [0,1] with size 1
• Free slot between meetings 0 and 1: [2,4] with size 2
• Free slot between meetings 1 and 2: [6,7] with size 1
• Free slot after meeting 2: [9,10] with size 1

Now we build pre (maximum free slot from start up to position i):

• pre[0] = 1 (free slot [0,1] before first meeting)
• pre[1] = max(1, 2) = 2 (comparing previous max with gap [2,4])
• pre[2] = max(2, 1) = 2 (comparing previous max with gap [6,7])

And suf (maximum free slot from position i to end):

• suf[2] = 1 (free slot [9,10] after last meeting)
• suf[1] = max(1, 1) = 1 (comparing next max with gap [6,7])
• suf[0] = max(1, 2) = 2 (comparing next max with gap [2,4])

Step 2: Evaluate each meeting for rescheduling

Meeting 0: [1,2]

• Left boundary l = 0, right boundary r = 4 (start of next meeting)
• Duration w = 2 - 1 = 1
• Option 1 (don't move): free space = 4 - 0 - 1 = 3
• Option 2 (move left): Not applicable (first meeting)
• Option 3 (move right): Check if suf[1] >= 1. Since suf[1] = 1, we can move it, creating free space = 4 - 0 = 4
• Best for this meeting: 4

Meeting 1: [4,6]

• Left boundary l = 2 (end of previous), right boundary r = 7 (start of next)
• Duration w = 6 - 4 = 2
• Option 1 (don't move): free space = 7 - 2 - 2 = 3
• Option 2 (move left): Check if pre[0] >= 2. Since pre[0] = 1 < 2, cannot move left
• Option 3 (move right): Check if suf[2] >= 2. Since suf[2] = 1 < 2, cannot move right
• Best for this meeting: 3

Meeting 2: [7,9]

• Left boundary l = 6 (end of previous), right boundary r = 10 (event end)
• Duration w = 9 - 7 = 2
• Option 1 (don't move): free space = 10 - 6 - 2 = 2
• Option 2 (move left): Check if pre[1] >= 2. Since pre[1] = 2, we can move it, creating free space = 10 - 6 = 4
• Option 3 (move right): Not applicable (last meeting)
• Best for this meeting: 4

Final Answer: 4

The maximum free time is 4, achieved by either:

• Moving meeting 0 to a later position (e.g., [6,7] or [9,10]), creating free space [0,4]
• Moving meeting 2 to an earlier position (e.g., [2,4]), creating free space [6,10]

This demonstrates how the algorithm efficiently finds the optimal rescheduling by considering each meeting's potential to create larger free periods when moved to existing gaps.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of several sequential operations:

• First loop to build the pre array: iterates through n-1 elements with O(1) operations per iteration → O(n)
• Second loop to build the suf array: iterates through n-1 elements with O(1) operations per iteration → O(n)
• Third loop to find the maximum free time: iterates through n elements with O(1) operations per iteration → O(n)

Since these loops run sequentially (not nested), the overall time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• pre array of size n → O(n)
• suf array of size n → O(n)
• A few constant variables (ans, l, r, w) → O(1)

The total space complexity is O(n) + O(n) + O(1) = O(n), where n is the number of meetings.

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

Common Pitfalls

1. Using 'elif' Instead of Independent 'if' Statements for Rescheduling Options

The Pitfall: In the provided code, there's a critical bug where elif is used to check if the meeting can be moved to a later gap:

# INCORRECT - using elif
if i > 0 and max_gap_before[i - 1] >= event_duration:
    max_free_time = max(max_free_time, right_boundary - left_boundary)
elif i + 1 < n and max_gap_after[i + 1] >= event_duration:  # Bug here!
    max_free_time = max(max_free_time, right_boundary - left_boundary)

This means if a meeting can be moved to an earlier gap, we never check if it can also be moved to a later gap. Both options should be evaluated independently since we want to consider all possible rescheduling scenarios.

The Solution: Use independent if statements to check both possibilities:

# CORRECT - using separate if statements
if i > 0 and max_gap_before[i - 1] >= event_duration:
    max_free_time = max(max_free_time, right_boundary - left_boundary)

if i + 1 < n and max_gap_after[i + 1] >= event_duration:
    max_free_time = max(max_free_time, right_boundary - left_boundary)

2. Forgetting to Consider Not Moving Any Meeting

The Pitfall: Another common mistake is forgetting to calculate the baseline maximum free time when no meetings are rescheduled. Some implementations might only look at rescheduling scenarios.

The Solution: Always initialize by finding the maximum free gap in the original schedule:

# Don't forget the base case - find max gap without moving anything
max_free_time = start_time[0]  # Gap before first meeting
for i in range(1, n):
    max_free_time = max(max_free_time, start_time[i] - end_time[i-1])
max_free_time = max(max_free_time, event_time - end_time[-1])  # Gap after last meeting

3. Incorrect Boundary Handling for Edge Meetings

The Pitfall: When calculating the free space created by moving the first or last meeting, developers might incorrectly use the general formula without considering the special boundaries:

# INCORRECT - not handling boundaries properly
left_boundary = end_time[i - 1]  # This fails when i = 0!
right_boundary = start_time[i + 1]  # This fails when i = n-1!

The Solution: Always check and handle edge cases explicitly:

# CORRECT - proper boundary handling
left_boundary = 0 if i == 0 else end_time[i - 1]
right_boundary = event_time if i == n - 1 else start_time[i + 1]

4. Off-by-One Errors in Precomputation Arrays

The Pitfall: When building the max_gap_before and max_gap_after arrays, it's easy to mess up the indices, especially in the backward iteration:

# INCORRECT - wrong range in backward iteration
for i in range(n - 1, 0, -1):  # Misses index 0!
    max_gap_after[i] = max(...)

The Solution: Ensure the ranges cover all necessary indices:

# CORRECT - proper range for backward iteration
for i in range(n - 2, -1, -1):  # Goes from n-2 down to 0
    max_gap_after[i] = max(
        max_gap_after[i + 1], 
        start_time[i + 1] - end_time[i]
    )