Skip to main content
Talentd

Reschedule Meetings for Maximum Free Time II - Solution & Explanation

MediumArrayGreedyEnumeration15 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 ith 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 <= 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].

Approach Overview

Problem Overview: You are given a list of non-overlapping meetings inside a fixed event timeline. You can reschedule exactly one meeting (keeping its duration the same) to any valid empty slot. The goal is to maximize the longest continuous free time interval after the reschedule.

Approach 1: Enumeration / Brute Force (O(n^2) time, O(1) space)

Try moving every meeting and evaluate the best place to relocate it. For meeting i, temporarily remove it and compute the merged free gap created between its neighbors. Then iterate through every other free gap to see if the meeting’s duration fits there. If it fits, you can place the meeting in that gap and keep the newly merged gap as free time. This approach relies on array iteration and explicit gap checking. It works for small inputs but becomes expensive because every meeting scans all other gaps.

Approach 2: Greedy with Gap Tracking (O(n) time, O(n) space)

Instead of recomputing gaps repeatedly, precompute all free gaps between meetings. Let gap[i] represent the free time before meeting i. When you remove meeting i, the gap between its neighbors becomes gap[i] + duration[i] + gap[i+1]. The key question: can the removed meeting fit somewhere else so this merged gap remains free?

Track the largest gaps to the left and right of each meeting using prefix and suffix maximum arrays. These allow constant-time checks for the largest available gap that does not touch meeting i. If any of those gaps can accommodate the meeting duration, the merged gap becomes the candidate free time. Otherwise, the meeting must be placed back inside the merged gap, reducing the free interval. This greedy observation avoids scanning all gaps repeatedly and turns the solution into a linear pass.

The algorithm mainly uses greedy reasoning with precomputed arrays and simple array traversal. Each meeting is evaluated once, and gap feasibility checks happen in O(1).

Recommended for interviews: Start by explaining the enumeration idea to show you understand how rescheduling affects neighboring gaps. Then move to the greedy optimization with prefix/suffix maximum gaps. Interviewers typically expect the O(n) solution because it demonstrates pattern recognition around gap merging, precomputation, and efficient enumeration.

Solution

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 = endTime[i] - startTime[i]. Then:

$ l_i = \begin{cases} 0 & i = 0 \\ endTime[i - 1] & i > 0 \end{cases}

r_i = \begin{cases} eventTime & i = n - 1 \\ startTime[i + 1] & i < n - 1 \end{cases}

The meeting can be moved to the left or right, and the free time in this case is:

r_i - l_i - w_i

If there exists a maximum free time on the left, pre_{i - 1}, such that pre_{i - 1} geq w_i, then meeting i can be moved to that position on the left, resulting in a new free time:

r_i - l_i

Similarly, if there exists a maximum free time on the right, suf_{i + 1}, such that suf_{i + 1} geq w_i, then meeting i can be moved to that position on the right, resulting in a new free time:

r_i - l_i

Therefore, we first preprocess two arrays, pre and suf, where pre[i] represents the maximum free time in the range [0, i], and suf[i] represents the maximum free time in the range [i, n - 1]. Then, for each meeting i, we calculate the maximum free time after moving it, and take the maximum value.

The time complexity is O(n), and the space complexity is O(n), where n$ is the number of meetings.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumeration / Brute ForceO(n^2)O(1)Useful for reasoning about how removing and relocating a meeting changes surrounding gaps
Greedy with Prefix/Suffix Max GapsO(n)O(n)Best for large inputs; evaluates each meeting once using precomputed largest gaps

Video Solution

Reschedule Meetings for Maximum Free Time II | Detailed Intuition | Leetcode 3440 | codestorywithMIK • codestorywithMIK • 11,473 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Reschedule Meetings for Maximum Free Time II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays