#3439

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Reschedule Meetings for Maximum Free Time I

Maximize free time by rescheduling up to k non-overlapping meetings within a fixed event using sliding window updates.

Problem Statement

You are given an integer eventTime representing the total duration of an event starting at time 0 and ending at time eventTime. Additionally, two integer arrays startTime and endTime describe n non-overlapping meetings, where the ith meeting occupies [startTime[i], endTime[i]].

You may reschedule at most k meetings by shifting their start times while keeping their durations fixed. Your goal is to maximize the longest continuous period of time without any meetings, effectively creating the maximum free time during the event.

Examples

Example 1

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

Output: 2

Reschedule the meeting at [1, 2] to [2, 3] , leaving no meetings during the time [0, 2] .

Example 2

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

Output: 6

Reschedule the meeting at [2, 4] to [1, 3] , leaving no meetings during the time [3, 9] .

Example 3

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

Output: 0

There is no time during the event not occupied by meetings.

Constraints

1 <= eventTime <= 109
n == startTime.length == endTime.length
2 <= n <= 105
1 <= k <= n
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Solution Approach

Sort and Identify Gaps

First, ensure meetings are sorted by start time. Calculate the gaps between consecutive meetings and at the boundaries. These gaps are candidates for free time, and identifying them upfront allows targeted rescheduling.

Sliding Window with Reschedule Count

Use a sliding window of K reschedulable meetings. Track the total occupied time and gaps within this window. Greedily move all meetings in the window to the start to maximize the free time after the window. Update running sums efficiently to avoid recomputation.

Track Maximum Free Time

For each window position, compute the free time after moving meetings. Compare it with the current maximum and update if larger. Continue sliding until all windows are evaluated. This approach ensures O(n) time complexity with O(1) extra space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each meeting is processed once in the sliding window. Space complexity is O(1) since only running sums and indices are stored, independent of n.

What Interviewers Usually Probe

Check if the candidate considers moving meetings versus just counting gaps.
Listen for awareness of linear-time updates rather than recomputing each scenario.
Notice if they handle edge gaps at the start and end of the event.

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider free time before the first or after the last meeting.
Recomputing sums naively for each rescheduling window, causing TLE.
Miscounting k moves or moving meetings without preserving their durations.

Follow-up variants

Allow meetings to be split or shortened to create more free time.
Maximize total free time sum instead of the single longest free period.
Limit rescheduling to consecutive meetings only.

FAQ

What is the main pattern used in Reschedule Meetings for Maximum Free Time I?

The primary pattern is sliding window with running state updates, focusing on gaps and reschedulable meetings.

Can I reschedule more than k meetings?

No, you are restricted to moving at most k meetings while keeping their durations fixed.

How do I handle the free time at the start or end of the event?

Include the gaps before the first and after the last meeting when computing maximum free time.

What is the time complexity of the optimal solution?

The optimal solution runs in O(n) time using a sliding window and O(1) extra space.

What common mistake should I avoid?

Avoid recomputing sums for each possible reschedule window and ensure meeting durations are preserved.

terminal

Solution

Solution 1: Sliding Window

The problem is essentially about merging adjacent free time intervals into a longer free interval. There are $n + 1$ free intervals in total:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxFreeTime(
        self, eventTime: int, k: int, startTime: List[int], endTime: List[int]
    ) -> int:
        nums = [startTime[0]]
        for i in range(1, len(endTime)):
            nums.append(startTime[i] - endTime[i - 1])
        nums.append(eventTime - endTime[-1])
        ans = s = 0
        for i, x in enumerate(nums):
            s += x
            if i >= k:
                ans = max(ans, s)
                s -= nums[i - k]
        return ans

Solution 2: Sliding Window (Space Optimization)

In Solution 1, we used an array to store the lengths of the free intervals. In fact, we do not need to store the entire array; we can use a function $f(i)$ to represent the length of the $i$-th free interval. This way, we can save space.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxFreeTime(
        self, eventTime: int, k: int, startTime: List[int], endTime: List[int]
    ) -> int:
        nums = [startTime[0]]
        for i in range(1, len(endTime)):
            nums.append(startTime[i] - endTime[i - 1])
        nums.append(eventTime - endTime[-1])
        ans = s = 0
        for i, x in enumerate(nums):
            s += x
            if i >= k:
                ans = max(ans, s)
                s -= nums[i - k]
        return ans

Continue Practicing

#3413 maximum coins from k consecutive bags #3086 minimum moves to pick k ones #2528 maximize the minimum powered city