# Reschedule Meetings for Maximum Free Time I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reschedule-meetings-for-maximum-free-time-i)
Canonical: https://scaleengineer.com/dsa/problems/reschedule-meetings-for-maximum-free-time-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You are given an integer `eventTime` denoting the duration of an event, where the event occurs from time `t = 0` to time `t = eventTime`.

You are also given two integer arrays `startTime` and `endTime`, each of length `n`. These represent the start and end time of `n` **non-overlapping** meetings, where the `ith` meeting occurs during the time `[startTime[i], endTime[i]]`.

You can reschedule **at most** `k` meetings by moving their start time while maintaining the **same duration**, to **maximize** the **longest** _continuous period of free time_ during the event.

The **relative** order of all the meetings should stay the _same_ and they should remain non-overlapping.

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.

**Example 1:**

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

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/reschedule-meetings-for-maximum-free-time-i/image0.png)

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

**Explanation:**

![](https://assets.glich.co/dsa/reschedule-meetings-for-maximum-free-time-i/image1.png)

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

**Explanation:**

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]`.

# Approaches
## Brute Force Calculation for All Gap Scenarios
This approach systematically checks every possible way to create a large free time gap. It considers the initial gaps between meetings and then, for each potential gap, calculates the maximum size it can be expanded to by rescheduling meetings on one or both sides, staying within the `k` move limit. This is done without any precomputation, leading to repeated calculations.
**Time:** O(N^2). The main loop iterates `N+1` times. Inside this loop, calculating costs and durations for prefixes and suffixes involves nested loops that take O(N) time in total. This results in a quadratic time complexity. · **Space:** O(N) to store the durations of the meetings. This can be optimized to O(1) if durations are calculated on the fly.
**Pros:** Conceptually straightforward, directly modeling the problem's scenarios.; Does not require complex data structures.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; Performs many redundant calculations for prefix/suffix costs and durations.
### Explanation
The algorithm first considers all initial free time intervals: `startTime[0]` (gap at the start), `eventTime - endTime[n-1]` (gap at the end), and `startTime[i] - endTime[i-1]` for `1 <= i < n`. The maximum of these is our baseline answer.

Then, for each potential gap (including those at the ends), we explore three possibilities of using our `k` moves:

1.  **Pack the prefix:** For a gap between meetings `i-1` and `i`, we can try to pack all meetings `0..i-1` to start at time 0. We calculate the cost (number of moves) for this by iterating through these meetings. If `cost <= k`, we calculate the new, larger gap: `startTime[i] - (end time of packed prefix)`.

2.  **Pack the suffix:** Similarly, we can try to pack all meetings `i..n-1` to end at `eventTime`. We calculate the cost and, if affordable, the new gap: `(start time of packed suffix) - endTime[i-1]`.

3.  **Pack both prefix and suffix:** We can try to pack both the prefix and suffix parts. We calculate the combined cost. If `cost <= k`, the new gap is `(start time of packed suffix) - (end time of packed prefix)`, which simplifies to `eventTime - total_duration`.

For each split point `i`, these calculations (costs and durations) are done by iterating through the relevant meetings. The overall maximum free time found across all these scenarios and all split points is the result.

```java
class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        if (n == 0) return eventTime;

        long[] durations = new long[n];
        for (int i = 0; i < n; i++) {
            durations[i] = (long)endTime[i] - startTime[i];
        }

        long maxFreeTime = 0;
        // Initial gaps
        maxFreeTime = Math.max(maxFreeTime, startTime[0]);
        maxFreeTime = Math.max(maxFreeTime, eventTime - endTime[n - 1]);
        for (int i = 1; i < n; i++) {
            maxFreeTime = Math.max(maxFreeTime, (long)startTime[i] - endTime[i - 1]);
        }

        for (int i = 0; i <= n; i++) {
            // Scenario 1: Pack prefix 0..i-1
            long prefixDuration = 0;
            int prefixCost = 0;
            long currentIdealStart = 0;
            for (int j = 0; j < i; j++) {
                if (startTime[j] != currentIdealStart) {
                    prefixCost++;
                }
                currentIdealStart += durations[j];
            }
            prefixDuration = currentIdealStart;
            if (prefixCost <= k) {
                long gap = (i < n) ? (long)startTime[i] - prefixDuration : (long)eventTime - prefixDuration;
                maxFreeTime = Math.max(maxFreeTime, gap);
            }

            // Scenario 2: Pack suffix i..n-1
            long suffixDuration = 0;
            for (int j = i; j < n; j++) {
                suffixDuration += durations[j];
            }
            int suffixCost = 0;
            long currentIdealStartSuffix = eventTime - suffixDuration;
            for (int j = i; j < n; j++) {
                if (startTime[j] != currentIdealStartSuffix) {
                    suffixCost++;
                }
                currentIdealStartSuffix += durations[j];
            }
            if (suffixCost <= k) {
                long gap = (i > 0) ? (eventTime - suffixDuration) - endTime[i - 1] : eventTime - suffixDuration;
                maxFreeTime = Math.max(maxFreeTime, gap);
            }

            // Scenario 3: Pack both
            if (prefixCost + suffixCost <= k) {
                long totalDuration = prefixDuration + suffixDuration;
                maxFreeTime = Math.max(maxFreeTime, eventTime - totalDuration);
            }
        }

        return (int)maxFreeTime;
    }
}
```
### Algorithm
1. Initialize `max_free_time` with the largest initial gap (at the start, end, or between any two meetings).
2. Pre-calculate the duration of each meeting.
3. Iterate through each possible split point `i` from `1` to `n` (for a gap after meeting `i-1`).
4. For each `i`, calculate the cost and duration of packing the prefix meetings `0..i-1` by iterating from `j=0` to `i-1`.
5. If the prefix packing cost is `≤ k`, calculate the new gap `startTime[i] - (packed_prefix_duration)` and update `max_free_time`.
6. Similarly, for each split point `i` from `0` to `n-1` (for a gap before meeting `i`), calculate the cost and duration of packing the suffix meetings `i..n-1`.
7. If the suffix packing cost is `≤ k`, calculate the new gap `(eventTime - packed_suffix_duration) - endTime[i-1]` and update `max_free_time`.
8. For each split point `i` from `0` to `n`, calculate the combined cost of packing both the prefix `0..i-1` and suffix `i..n-1`.
9. If the combined cost is `≤ k`, calculate the gap `eventTime - total_duration` and update `max_free_time`.
10. Return the final `max_free_time`.

## Linear Time Solution with Precomputation
This approach significantly optimizes the brute-force method by pre-calculating all necessary values. Instead of re-computing prefix/suffix durations and their associated rescheduling costs in each iteration, we compute them once and store them in auxiliary arrays. This allows us to evaluate each potential gap scenario in constant time, reducing the overall complexity from quadratic to linear.
**Time:** O(N). The precomputation steps each take a single pass over the `N` meetings, which is `O(N)`. The final loop to check all scenarios also runs `N+1` times, with each step being `O(1)`. The total time complexity is dominated by these linear passes. · **Space:** O(N) for storing the four precomputed arrays: `prefixSumDur`, `prefixMoves`, `suffixSumDur`, and `suffixMoves`.
**Pros:** Highly efficient with linear time complexity, suitable for large inputs.; Systematically covers all optimal arrangements for creating a single large gap.
**Cons:** Requires extra space for the precomputed arrays.
### Explanation
The `O(N^2)` approach is slow due to redundant calculations. We can optimize it by precomputing the required values. We use four arrays for this:

1.  `prefix_sum_dur[i]`: Stores the total duration of meetings `0` to `i-1`.
2.  `prefix_moves[i]`: Stores the cost (number of moves) to pack meetings `0` to `i-1` tightly at the start.
3.  `suffix_sum_dur[i]`: Stores the total duration of meetings `i` to `n-1`.
4.  `suffix_moves[i]`: Stores the cost to pack meetings `i` to `n-1` tightly at the end.

These arrays can all be computed in `O(N)` time. Once we have them, we can iterate through all split points `i` from `0` to `n` and check the three packing scenarios (prefix only, suffix only, both) in `O(1)` time for each split.

- **Initial Gaps:** We first find the maximum of all initial gaps.
- **Pack Prefix:** If `prefix_moves[i] <= k`, the new gap is `startTime[i] - prefix_sum_dur[i]` (or `eventTime - prefix_sum_dur[i]` if `i=n`).
- **Pack Suffix:** If `suffix_moves[i] <= k`, the new gap is `(eventTime - suffix_sum_dur[i]) - endTime[i-1]` (or `eventTime - suffix_sum_dur[i]` if `i=0`).
- **Pack Both:** If `prefix_moves[i] + suffix_moves[i] <= k`, the new gap is `eventTime - (prefix_sum_dur[i] + suffix_sum_dur[i])`.

By checking all these possibilities, we find the maximum achievable free time.

```java
class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        if (n == 0) return eventTime;

        long[] durations = new long[n];
        for (int i = 0; i < n; i++) {
            durations[i] = (long)endTime[i] - startTime[i];
        }

        long[] prefixSumDur = new long[n + 1];
        int[] prefixMoves = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSumDur[i] = prefixSumDur[i - 1] + durations[i - 1];
            prefixMoves[i] = prefixMoves[i - 1];
            if (startTime[i - 1] != prefixSumDur[i - 1]) {
                prefixMoves[i]++;
            }
        }

        long[] suffixSumDur = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSumDur[i] = suffixSumDur[i + 1] + durations[i];
        }

        int[] suffixMoves = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixMoves[i] = suffixMoves[i + 1];
            long idealStartTime = (long)eventTime - suffixSumDur[i];
            if (startTime[i] != idealStartTime) {
                suffixMoves[i]++;
            }
        }

        long maxFreeTime = 0;
        maxFreeTime = Math.max(maxFreeTime, startTime[0]);
        maxFreeTime = Math.max(maxFreeTime, eventTime - endTime[n - 1]);
        for (int i = 1; i < n; i++) {
            maxFreeTime = Math.max(maxFreeTime, (long)startTime[i] - endTime[i - 1]);
        }

        for (int i = 0; i <= n; i++) {
            if (prefixMoves[i] <= k) {
                long gap = (i < n) ? (long)startTime[i] - prefixSumDur[i] : (long)eventTime - prefixSumDur[i];
                maxFreeTime = Math.max(maxFreeTime, gap);
            }
            if (suffixMoves[i] <= k) {
                long gap = (i > 0) ? (eventTime - suffixSumDur[i]) - endTime[i - 1] : eventTime - suffixSumDur[i];
                maxFreeTime = Math.max(maxFreeTime, gap);
            }
            if (prefixMoves[i] + suffixMoves[i] <= k) {
                long totalDuration = prefixSumDur[i] + suffixSumDur[i];
                maxFreeTime = Math.max(maxFreeTime, eventTime - totalDuration);
            }
        }

        return (int)maxFreeTime;
    }
}
```
### Algorithm
1. Pre-calculate `durations` for all meetings in `O(N)`.
2. Pre-calculate `prefix_sum_dur` and `prefix_moves` arrays in a single `O(N)` pass from left to right.
3. Pre-calculate `suffix_sum_dur` and `suffix_moves` arrays in a single `O(N)` pass from right to left.
4. Initialize `max_free_time` with the largest initial gap in the schedule.
5. Iterate through all split points `i` from `0` to `n`.
6. For each split, use the precomputed arrays to find the costs and durations for three scenarios in `O(1)` time:
   a. Packing only the prefix.
   b. Packing only the suffix.
   c. Packing both prefix and suffix.
7. If a scenario's cost is within the `k` limit, calculate the resulting free time and update `max_free_time`.
8. Return the final `max_free_time`.