#3440

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Reschedule Meetings for Maximum Free Time II

Maximize free time by rescheduling at most one meeting using a greedy choice with invariant validation approach for arrays.

array greedy enumeration

Problem Statement

You are given an integer eventTime representing the total duration of an event and two integer arrays startTime and endTime of length n. Each element in startTime and endTime defines a non-overlapping meeting within [0, eventTime], where the ith meeting occurs from startTime[i] to endTime[i].

You are allowed to reschedule at most one meeting by shifting its start time while keeping the duration constant, ensuring meetings remain non-overlapping. Your goal is to determine the maximum possible continuous free time interval within the event after performing at most one reschedule.

Examples

Example 1

Input: eventTime = 5, 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, startTime = [0,7,9], endTime = [1,8,10]

Output: 7

Reschedule the meeting at [0, 1] to [8, 9] , leaving no meetings during the time [0, 7] .

Example 3

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

Output: 6

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

Constraints

1 <= eventTime <= 109
n == startTime.length == endTime.length
2 <= n <= 105
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

Start by confirming meetings are sorted by startTime. Compute initial gaps between consecutive meetings and at the edges [0, first meeting] and [last meeting, eventTime]. This establishes baseline free intervals.

Greedy Rescheduling

Iterate over each meeting to consider moving it earlier or later. For each candidate, check the longest free interval achievable while maintaining non-overlap. Select the reschedule that maximizes the continuous free period.

Invariant Validation

After proposing a reschedule, validate that all meetings remain non-overlapping. Update the maximum free time only if the new arrangement satisfies the invariant constraints, ensuring correctness without full recomputation.

Complexity Analysis

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

Time complexity is O(n) as each meeting is evaluated once for potential rescheduling. Space complexity is O(1) if only tracking current maximum gaps without additional arrays.

What Interviewers Usually Probe

Checking if the candidate meeting can extend the largest gap indicates awareness of greedy optimization.
Confirming non-overlapping constraints after rescheduling shows understanding of invariant maintenance.
Evaluating all possible single reschedules signals thorough exploration of array-based solutions.

Common Pitfalls or Variants

Common pitfalls

Forgetting to maintain the duration of the rescheduled meeting, which can invalidate gaps.
Overlooking edge gaps at the start or end of the event when computing maximum free time.
Assuming multiple meetings can be moved instead of only one, violating problem constraints.

Follow-up variants

Allow rescheduling multiple meetings to maximize free time using a dynamic greedy approach.
Determine minimum total idle time instead of maximum free interval with a similar rescheduling strategy.
Consider meetings with flexible durations, adjusting both start and end times under non-overlap constraints.

FAQ

What is the core pattern in Reschedule Meetings for Maximum Free Time II?

The core pattern is a greedy choice plus invariant validation, focusing on rescheduling one meeting to maximize continuous free time.

Can multiple meetings be rescheduled?

No, the problem limits rescheduling to at most one meeting while maintaining all non-overlapping constraints.

How do I compute maximum free time efficiently?

Track gaps between meetings and evaluate each meeting's potential shift using a greedy approach to maximize the largest gap.

Do I need to sort meetings first?

Yes, sorting by startTime ensures gap calculations and rescheduling validations are efficient and correct.

What common mistake should I avoid?

A common error is ignoring edge intervals or violating the non-overlapping constraint when moving a meeting.

terminal

Solution

Solution 1: Greedy

According to the problem description, for meeting $i$, let $l_i$ be the non-free position to its left, $r_i$ be the non-free position to its right, and let the duration of meeting $i$ be $w_i = \text{endTime}[i] - \text{startTime}[i]$. Then:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def maxFreeTime(
        self, eventTime: int, startTime: List[int], endTime: List[int]
    ) -> int:
        n = len(startTime)
        pre = [0] * n
        suf = [0] * n
        pre[0] = startTime[0]
        suf[n - 1] = eventTime - endTime[-1]
        for i in range(1, n):
            pre[i] = max(pre[i - 1], startTime[i] - endTime[i - 1])
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], startTime[i + 1] - endTime[i])
        ans = 0
        for i in range(n):
            l = 0 if i == 0 else endTime[i - 1]
            r = eventTime if i == n - 1 else startTime[i + 1]
            w = endTime[i] - startTime[i]
            ans = max(ans, r - l - w)
            if i and pre[i - 1] >= w:
                ans = max(ans, r - l)
            elif i + 1 < n and suf[i + 1] >= w:
                ans = max(ans, r - l)
        return ans

Continue Practicing

#3434 maximum frequency after subarray operation #3588 find maximum area of a triangle #3630 partition array for maximum xor and and