LeetCode 3439 - Reschedule Meetings for Maximum Free Time I

We are given an event that runs from time 0 to eventTime. Inside this event there are n non-overlapping meetings, already arranged in chronological order.

leetcodemediumarraygreedysliding-window

LeetCode Problem 3439

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sliding Window

Solution

Problem Understanding

We are given an event that runs from time 0 to eventTime. Inside this event there are n non-overlapping meetings, already arranged in chronological order.

Each meeting i occupies the interval:

[startTime[i], endTime[i]]

The meetings do not overlap, and the input guarantees:

endTime[i] <= startTime[i + 1]

which means there may be free time between meetings.

We are allowed to reschedule at most k meetings. When a meeting is rescheduled:

  • Its duration must remain unchanged.
  • The relative order of all meetings must remain the same.
  • Meetings must still not overlap.
  • Meetings must remain inside the event interval [0, eventTime].

Our goal is to maximize the length of the longest continuous free interval after performing at most k reschedulings.

A useful way to think about the problem is that the meetings partition the timeline into gaps of free time. Rescheduling meetings does not change meeting durations, it only changes where those durations sit within the timeline. The key question becomes: how much existing free time can be merged into one larger continuous block?

The constraints are important:

  • n can be as large as 100,000.
  • eventTime can be as large as 10^9.

Because n is large, any algorithm worse than linear or near-linear time will be too slow. We need an O(n) or O(n log n) solution.

Several edge cases are worth noticing immediately:

  • There may be no free time at all.
  • The largest free interval may occur before the first meeting or after the last meeting.
  • k may be as large as n.
  • Meetings can already be tightly packed together.
  • Free gaps can be zero length.

The non-overlapping and sorted guarantees are extremely helpful because they allow us to reason about consecutive gaps without worrying about reordering meetings.

Approaches

Brute Force

A brute force approach would attempt to enumerate which meetings are rescheduled and where they are moved.

For every subset of up to k meetings, we could try to reposition them while preserving order and non-overlap, then compute the resulting largest free interval.

This approach is correct because it explores all valid arrangements. However, it is completely impractical. There are exponentially many subsets of meetings, and each meeting could potentially be moved to many different positions.

Even with aggressive pruning, the search space grows far too quickly for n = 100,000.

Key Observation

Instead of focusing on meetings, focus on the free gaps between meetings.

Define:

  • Gap before the first meeting.
  • Gap between every pair of consecutive meetings.
  • Gap after the last meeting.

This gives exactly n + 1 gaps.

Suppose we choose a consecutive block of k meetings and move them so that they become tightly packed against one side. Doing so removes the free gaps around those meetings and merges all the free time from the surrounding region into one continuous interval.

If we move k consecutive meetings, we can merge exactly k + 1 consecutive gaps into one larger gap.

Therefore, the problem reduces to:

Find the maximum sum of k + 1 consecutive gaps.

Once viewed this way, the solution becomes a simple sliding window over the gap array.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates meeting movements and arrangements
Optimal O(n) O(n) Build gaps and find maximum sum of k + 1 consecutive gaps

Algorithm Walkthrough

Step 1: Build the gap array

Create an array gaps of length n + 1.

The first gap is the free time before the first meeting:

gaps[0] = startTime[0]

For each pair of adjacent meetings:

gaps[i] = startTime[i] - endTime[i - 1]

Finally, add the gap after the last meeting:

gaps[n] = eventTime - endTime[n - 1]

Step 2: Understand what one rescheduling does

Moving a meeting allows the free space on both sides of that meeting to be combined.

If we move multiple consecutive meetings, we can compress them together and merge all surrounding free intervals into one continuous free block.

Moving k consecutive meetings merges k + 1 consecutive gaps.

Step 3: Convert the problem

The longest free interval obtainable equals the largest sum of any contiguous block of k + 1 gaps.

So we need:

max(
    gaps[i] + gaps[i+1] + ... + gaps[i+k]
)

for every valid starting position.

Step 4: Use a sliding window

Compute the sum of the first k + 1 gaps.

Then slide the window one position at a time:

  • Add the new gap entering the window.
  • Remove the gap leaving the window.
  • Update the maximum sum seen.

This processes all candidate merged intervals in linear time.

Step 5: Return the maximum window sum

The maximum window sum is the answer.

Why it works

Each rescheduled meeting can eliminate one boundary separating adjacent free gaps. Rescheduling k consecutive meetings eliminates exactly k such boundaries, allowing k + 1 consecutive gaps to merge into one continuous free interval.

Conversely, any continuous free interval obtained after at most k reschedulings must come from merging at most k + 1 consecutive original gaps. Therefore every valid solution corresponds to a window of k + 1 gaps, and every such window is achievable.

Thus the problem is exactly equivalent to finding the maximum sum of k + 1 consecutive gaps. The problem asks us to find the maximum continuous free time during a scheduled event when we are allowed to reschedule at most k meetings. We are given the total eventTime as the time window [0, eventTime] and two arrays, startTime and endTime, representing non-overlapping meetings. Each meeting can only be shifted in time if its duration is preserved and the relative order of meetings remains the same. The goal is to maximize the longest period during which no meeting occurs.

The input represents:

  • eventTime: the total duration of the event.
  • startTime[i] and endTime[i]: the start and end times of the ith meeting.
  • k: the maximum number of meetings we can move to optimize free time.

The output is a single integer representing the maximum continuous free period achievable by rescheduling up to k meetings.

Constraints indicate:

  • Up to 10^5 meetings, so brute-force enumeration of all rescheduling options is infeasible.
  • Meetings are sorted and non-overlapping.
  • eventTime can be very large (10^9), so solutions that iterate over time slots are too slow.
  • Rescheduling must maintain order and duration, which strongly limits feasible moves.

Important edge cases include:

  • k >= n: effectively all meetings could be shifted, allowing maximal free time anywhere.
  • Meetings filling the event completely: no free time is possible.
  • Small gaps at the edges (start 0 or end eventTime) may be the optimal free period after rescheduling.

Approaches

Brute Force: One could consider trying all possible combinations of k meetings to reschedule and shift them within all valid positions, then compute the longest free period for each. This method is correct because it explicitly considers every feasible arrangement. However, with n up to 10^5 and k up to n, the number of combinations is combinatorial (C(n, k)), making this approach infeasible.

Key Insight: Since meetings are non-overlapping and must retain order, the problem reduces to identifying the k smallest gaps between meetings and moving the adjacent meetings to consolidate free time. By sliding windows over gaps and adjusting the k meetings closest to the desired free period, we can efficiently compute the maximum continuous free period without enumerating all reschedulings.

Approach Time Complexity Space Complexity Notes
Brute Force O(n choose k * n) O(n) Enumerates all reschedulings; infeasible for large n
Optimal O(n) O(n) Computes gaps and uses sliding window to consolidate free periods efficiently

Algorithm Walkthrough

  1. Compute the duration of each meeting dur[i] = endTime[i] - startTime[i]. This allows rescheduling while preserving durations.
  2. Compute the gaps between consecutive meetings including the start and end edges: gap[0] = startTime[0] - 0, gap[i] = startTime[i] - endTime[i-1], and gap[n] = eventTime - endTime[n-1].
  3. Identify all gaps that can be increased by rescheduling meetings. Because the order must remain, moving a meeting rightward extends the previous gap; moving leftward extends the next gap.
  4. Using a sliding window of size k, simulate moving up to k meetings to consolidate adjacent gaps. For each possible window of k meetings, calculate the sum of gaps outside the moved meetings.
  5. Track the maximum continuous free time found across all windows.

Why it works: The algorithm works because the largest free period occurs either at an edge or by consolidating gaps via rescheduling the smallest set of meetings. Non-overlapping constraints and fixed durations prevent any other arrangement, so scanning over sliding windows of k consecutive movable meetings guarantees the optimal solution.

Python Solution

from typing import List

class Solution:
    def maxFreeTime(
        self,
        eventTime: int,
        k: int,
        startTime: List[int],
        endTime: List[int]
    ) -> int:
        n = len(startTime)

        gaps = [0] * (n + 1)

        gaps[0] = startTime[0]

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

        gaps[n] = eventTime - endTime[-1]

        window_size = k + 1

        current_sum = sum(gaps[:window_size])
        answer = current_sum

        for right in range(window_size, n + 1):
            current_sum += gaps[right]
            current_sum -= gaps[right - window_size]
            answer = max(answer, current_sum)

        return answer

The implementation starts by constructing the gaps array. These gaps represent every free interval in the schedule, including the free time before the first meeting and after the last meeting.

Once the gaps are available, the problem becomes finding the maximum sum of k + 1 consecutive gaps. The code initializes a sliding window covering the first k + 1 gaps and computes its sum.

The window is then moved across the array. Each move updates the running sum in constant time by adding the incoming gap and removing the outgoing gap. The maximum window sum encountered is stored in answer.

Because every valid solution corresponds to merging k + 1 consecutive gaps, the largest window sum is exactly the maximum achievable free interval. def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int: n = len(startTime) # Compute initial gaps including edges gaps = [startTime[0]] + [startTime[i] - endTime[i-1] for i in range(1, n)] + [eventTime - endTime[-1]]

    if k >= n:
        # We can move all meetings to one side, free time is total eventTime minus total duration
        total_meeting_time = sum(endTime[i] - startTime[i] for i in range(n))
        return eventTime - total_meeting_time
    
    # Precompute prefix sums of gaps for quick window sum calculation
    prefix_gaps = [0]
    for g in gaps:
        prefix_gaps.append(prefix_gaps[-1] + g)
    
    max_free = 0
    # Consider all windows of k consecutive meetings to "move"
    for i in range(n - k + 1):
        # Sum of gaps outside the k moved meetings
        free_before = prefix_gaps[i+1]  # gaps before window
        free_after = prefix_gaps[-1] - prefix_gaps[i + k + 1]  # gaps after window
        max_free = max(max_free, free_before, free_after)
    
    return max_free


**Explanation:** The solution computes gaps, handles the trivial case when all meetings can be moved, and then uses prefix sums to efficiently compute the maximal free time resulting from moving any `k` consecutive meetings. Sliding windows ensure the order constraint is respected.

## Go Solution

```go
func maxFreeTime(eventTime int, k int, startTime []int, endTime []int) int {
	n := len(startTime)

	gaps := make([]int, n+1)

	gaps[0] = startTime[0]

	for i := 1; i < n; i++ {
		gaps[i] = startTime[i] - endTime[i-1]
	}

	gaps[n] = eventTime - endTime[n-1]

	windowSize := k + 1

	currentSum := 0
	for i := 0; i < windowSize; i++ {
		currentSum += gaps[i]
	}

	answer := currentSum

	for right := windowSize; right <= n; right++ {
		currentSum += gaps[right]
		currentSum -= gaps[right-windowSize]

		if currentSum > answer {
			answer = currentSum
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

The gap array is stored in a slice of length n + 1. The sliding window sum is maintained using integer arithmetic, which is safe because the largest possible answer is at most eventTime, and eventTime ≤ 10^9, well within Go's int range on LeetCode platforms.

No special handling for nil slices is required because the constraints guarantee at least two meetings.

Worked Examples

Example 1

Input

eventTime = 5
k = 1
startTime = [1,3]
endTime = [2,5]

Build gaps

Gap Value
Before first meeting 1
Between meetings 1
After last meeting 0 
gaps = [1, 1, 0]

Window size:

k + 1 = 2

Sliding Window

Window Sum
[1,1] 2
[1,0] 1

Maximum:

2

Answer:

2

Example 2

Input

eventTime = 10
k = 1
startTime = [0,2,9]
endTime = [1,4,10]

Build gaps

Gap Value
Before first 0
Between first and second 1
Between second and third 5
After last 0 
gaps = [0, 1, 5, 0]

Window size:

2

Sliding Window

Window Sum
[0,1] 1
[1,5] 6
[5,0] 5

Maximum:

6

Answer:

6

Example 3

Input

eventTime = 5
k = 2
startTime = [0,1,2,3,4]
endTime = [1,2,3,4,5]

Build gaps

gaps = [0, 0, 0, 0, 0, 0]

Window size:

3

Every window sum is:

0

Answer:

0

n := len(startTime)
gaps := make([]int, n+1)
gaps[0] = startTime[0]
for i := 1; i < n; i++ {
    gaps[i] = startTime[i] - endTime[i-1]
}
gaps[n] = eventTime - endTime[n-1]

if k >= n {
    totalMeeting := 0
    for i := 0; i < n; i++ {
        totalMeeting += endTime[i] - startTime[i]
    }
    return eventTime - totalMeeting
}

prefix := make([]int, n+2)
for i := 0; i <= n; i++ {
    prefix[i+1] = prefix[i] + gaps[i]
}

maxFree := 0
for i := 0; i <= n-k; i++ {
    freeBefore := prefix[i+1]
    freeAfter := prefix[n+1] - prefix[i+k+1]
    if freeBefore > maxFree {
        maxFree = freeBefore
    }
    if freeAfter > maxFree {
        maxFree = freeAfter
    }
}
return maxFree

}


**Go Notes:** We use slices for gaps and prefix sums. Go requires explicit slice allocation. Integer overflow is not a concern as `eventTime` fits in `int`. Logic mirrors Python.

## Worked Examples

**Example 1:** `eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]`

- `gaps = [1, 1, 0]`
- Sliding window of `k=1`:

- Move first meeting: free_before = 1, free_after = 0 → max 1
- Move second meeting: free_before = 2, free_after = 0 → max 2
- Output = 2

**Example 2:** `eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]`

- `gaps = [0,1,5,0]`
- Move each meeting:

- First: free_before = 0, free_after = 5 → max 5
- Second: free_before = 1, free_after = 0 → max 5
- Third: free_before = 2, free_after = 0 → max 6
- Output = 6

**Example 3:** `eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]`

- `gaps = [0,0,0,0,0,0]`
- Any moves do not create free space → max_free = 0

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | One pass to build gaps and one pass for sliding window |
| Space | O(n) | Stores the `n + 1` gap values |

The gap construction requires linear time. The sliding window also scans the gap array exactly once. Therefore the total running time is `O(n)`.

The only auxiliary structure is the gap array of size `n + 1`, giving `O(n)` extra space.

## Test Cases

```python
from typing import List

s = Solution()

assert s.maxFreeTime(5, 1, [1, 3], [2, 5]) == 2      # example 1
assert s.maxFreeTime(10, 1, [0, 2, 9], [1, 4, 10]) == 6  # example 2
assert s.maxFreeTime(5, 2, [0, 1, 2, 3, 4], [1, 2, 3, 4, 5]) == 0  # example 3

assert s.maxFreeTime(10, 1, [2, 6], [4, 8]) == 4    # large edge gap at start
assert s.maxFreeTime(10, 1, [0, 4], [2, 8]) == 4    # large edge gap at end

assert s.maxFreeTime(20, 2, [2, 6, 12], [4, 8, 14]) == 12  # merge three gaps

assert s.maxFreeTime(100, 3, [10, 20, 30, 40], [15, 25, 35, 45]) == 80  # k near n

assert s.maxFreeTime(8, 1, [0, 7], [1, 8]) == 6     # single interior gap

assert s.maxFreeTime(6, 1, [0, 1, 5], [1, 2, 6]) == 3  # mixed zero and non-zero gaps

assert s.maxFreeTime(15, 2, [1, 5, 10], [2, 6, 11]) == 13  # maximum window in middle

Test Summary

Test Why
Example 1 Basic validation
Example 2 Large internal free interval
Example 3 No free time exists
Large start gap Ensures leading gap is included
Large end gap Ensures trailing gap is included
Merge three gaps Verifies k + 1 gap merging
k near n Stress test for large merge window
Single interior gap Minimal free-space structure
Mixed zero gaps Tests zero-length intervals
Maximum window in middle Ensures sliding window finds interior optimum

Edge Cases

No Free Time Anywhere

A schedule may completely fill the event duration.

For example:

start = [0,1,2,3]
end   = [1,2,3,4]

Every gap is zero. A buggy solution might assume some positive free interval can always be created through rescheduling. In reality, the total free time is zero, so the answer must remain zero. The gap-array formulation handles this naturally because every window sum is zero.

Largest Gap at the Boundary

The optimal free interval may involve the gap before the first meeting or after the last meeting.

For example:

eventTime = 10
start = [5, 8]
end = [6, 9]

The free time before the first meeting is very large. Implementations that only consider gaps between meetings would miss the correct answer. The algorithm explicitly stores both boundary gaps as part of the gaps array.

Very Large k

When k approaches n, the sliding window size becomes almost the entire gap array.

For example:

k = n

The window size becomes:

n + 1

which covers every gap. The answer becomes the sum of all gaps, meaning all free time can be consolidated into one interval. The implementation handles this correctly because the initial window already spans the entire gap array and no further sliding is required. | Time | O(n) | Single pass to compute gaps, prefix sums, and sliding window evaluation | | Space | O(n) | Store gaps and prefix sums arrays |

The algorithm is linear in n because each step (gap computation, prefix sum, sliding window) is a single scan.

Test Cases

# Provided examples
assert Solution().maxFreeTime(5, 1, [1,3], [2,5]) == 2  # reschedule first meeting
assert Solution().maxFreeTime(10, 1, [0,2,9], [1,4,10]) == 6  # reschedule last meeting