Is Reschedule Meetings for Maximum Free Time II easy or hard?

The problem is rated Medium because the core idea—removing one meeting and analyzing gap changes—is simple, but achieving the optimal O(n) solution requires recognizing the prefix/suffix maximum gap optimization.

Reschedule Meetings for Maximum Free Time II Python/Java solution

Most implementations follow the same greedy idea: compute gap lengths, build prefix and suffix maximum arrays, and iterate through meetings to test the effect of moving each one. The logic translates directly across Python, Java, C++, Go, TypeScript, and Rust.

How to solve Reschedule Meetings for Maximum Free Time II in O(n)?

First compute all free gaps between consecutive meetings. Build prefix and suffix arrays that store the maximum gap seen so far from the left and right. For each meeting, calculate the merged gap formed after removing it, then check if another gap can fit the meeting duration. These constant-time checks make the overall algorithm linear.

What is the best approach for Reschedule Meetings for Maximum Free Time II?

The optimal approach uses a greedy strategy with precomputed free gaps. Compute all gaps between meetings, then use prefix and suffix maximum arrays to track the largest available gap excluding the current meeting. For each meeting, simulate removing it and check whether its duration fits into another gap. This reduces the solution to O(n) time and O(n) space.

Is Reschedule Meetings for Maximum Free Time II asked at Google/Amazon/Meta?

Greedy interval scheduling and gap maximization problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving meeting rescheduling, merging intervals, and maximizing free time are common interview patterns.

What data structure is used in Reschedule Meetings for Maximum Free Time II?

The solution mainly uses arrays to store meeting times and gap lengths. Prefix and suffix maximum arrays help track the largest available free interval efficiently while evaluating each meeting.

What is the time complexity of Reschedule Meetings for Maximum Free Time II?

The optimal greedy solution runs in O(n) time because each meeting is evaluated once while prefix and suffix maximum gaps allow constant-time checks. Space complexity is O(n) for storing gap arrays and prefix/suffix maximum values.

Description Hints 1 Solution Video 43:57

3440. Reschedule Meetings for Maximum Free Time II

Medium60.4% acceptance4 companies

You are given an integer eventTime denoting the duration of an event. You are also given two integer arrays startTime and endTime, each of length n.

These represent the start and end times of n non-overlapping meetings that occur during the event between time t = 0 and time t = eventTime, where the i^th meeting occurs during the time [startTime[i], endTime[i]].

You can reschedule at most one meeting by moving its start time while maintaining the same duration, such that the meetings remain non-overlapping, to maximize the longest continuous period of free time during the event.

Return the maximum amount of free time possible after rearranging the meetings.

Note that the meetings can not be rescheduled to a time outside the event and they should remain non-overlapping.

Note: In this version, it is valid for the relative ordering of the meetings to change after rescheduling one meeting.

Example 1:

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

Output: 2

Explanation:

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

Explanation:

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

Explanation:

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

Example 4:

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

Output: 0

Explanation:

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

Constraints:

1 <= eventTime <= 10⁹
n == startTime.length == endTime.length
2 <= n <= 10⁵
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Asked at 4 companies

Google Amazon Microsoft Bloomberg

Topics

Hints open one at a time

Hint 1

If we reschedule a meeting earlier or later, we need to find a gap of length at least endTime[i] - startTime[i]. Try maintaining the gaps in some sorted data structure.

43:57

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

5
[1,3]
[2,5]

Input

10
[0,7,9]
[1,8,10]

Input

10
[0,3,7,9]
[1,4,8,10]

Input

5
[0,1,2,3,4]
[1,2,3,4,5]

Your code is saved on this device.Solution