Reschedule Meetings for Maximum Free Time II
Source: leetcode
Difficulty: Medium
Tags: array, greedy, enumeration

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:**


![](https://assets.leetcode.com/uploads/2024/12/22/example0_rescheduled.png)


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:**


![](https://assets.leetcode.com/uploads/2024/12/22/rescheduled_example0.png)


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:**


**![](https://assets.leetcode.com/uploads/2025/01/28/image3.png)**


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




C++ solution:
class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<int> gaps(n + 1);
        gaps[0] = startTime[0];
        for (int i = 1; i < n; ++i) {
            gaps[i] = startTime[i] - endTime[i-1];
        }
        gaps[n] = eventTime - endTime[n-1];
        
        int original_max = 0;
        for (int g : gaps) {
            original_max = max(original_max, g);
        }
        
        vector<int> prefix_max(n+1);
        prefix_max[0] = gaps[0];
        for (int i = 1; i <= n; ++i) {
            prefix_max[i] = max(prefix_max[i-1], gaps[i]);
        }
        
        vector<int> suffix_max(n+1);
        suffix_max[n] = gaps[n];
        for (int i = n-1; i >= 0; --i) {
            suffix_max[i] = max(suffix_max[i+1], gaps[i]);
        }
        
        int res = original_max;
        
        for (int i = 0; i < n; ++i) {
            int merged_gap;
            if (i == 0) {
                merged_gap = startTime[1];
            } else if (i == n-1) {
                merged_gap = eventTime - endTime[n-2];
            } else {
                merged_gap = startTime[i+1] - endTime[i-1];
            }
            
            int x = i;
            int y = i + 1;
            int left_part_max = (x == 0) ? 0 : prefix_max[x-1];
            int right_part_max = (y+1 > n) ? 0 : suffix_max[y+1];
            int other_max = max(left_part_max, right_part_max);
            
            int d_i = endTime[i] - startTime[i];
            
            int option1 = 0;
            if (other_max >= d_i) {
                option1 = max(merged_gap, other_max - d_i);
            }
            
            int option2 = 0;
            if (merged_gap >= d_i) {
                option2 = max(merged_gap - d_i, other_max);
            }
            
            res = max(res, max(option1, option2));
        }
        
        return res;
    }
};

Go solution:
func maxFreeTime(eventTime int, startTime []int, endTime []int) int {
    n := len(startTime)
    if n == 0 {
        return eventTime
    }

    gaps := make([]int, n+1)
    gaps[0] = startTime[0] - 0
    for j := 1; j < n; j++ {
        gaps[j] = startTime[j] - endTime[j-1]
    }
    gaps[n] = eventTime - endTime[n-1]

    prefixMax := make([]int, n+1)
    prefixMax[0] = gaps[0]
    for j := 1; j <= n; j++ {
        prefixMax[j] = max(prefixMax[j-1], gaps[j])
    }

    suffixMax := make([]int, n+1)
    suffixMax[n] = gaps[n]
    for j := n - 1; j >= 0; j-- {
        suffixMax[j] = max(suffixMax[j+1], gaps[j])
    }

    originalMax := 0
    for _, g := range gaps {
        if g > originalMax {
            originalMax = g
        }
    }

    maxCandidate := originalMax

    for i := 0; i < n; i++ {
        var mergedGap int
        if i == 0 {
            mergedGap = startTime[1] - 0
        } else if i == n-1 {
            mergedGap = eventTime - endTime[i-1]
        } else {
            mergedGap = startTime[i+1] - endTime[i-1]
        }

        d := endTime[i] - startTime[i]
        var maxOtherGap int

        if i == 0 {
            maxOtherGap = suffixMax[2]
        } else if i == n-1 {
            maxOtherGap = prefixMax[n-2]
        } else {
            leftMax := prefixMax[i-1]
            rightMax := suffixMax[i+2]
            maxOtherGap = max(leftMax, rightMax)
        }

        currentCandidate := 0
        if mergedGap >= d {
            candidate1 := max(mergedGap-d, maxOtherGap)
            if candidate1 > currentCandidate {
                currentCandidate = candidate1
            }
        }
        if maxOtherGap >= d {
            candidate2 := max(mergedGap, maxOtherGap-d)
            if candidate2 > currentCandidate {
                currentCandidate = candidate2
            }
        }

        if currentCandidate > maxCandidate {
            maxCandidate = currentCandidate
        }
    }

    return maxCandidate
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Java solution:
class Solution {
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] gaps = new int[n + 1];
        gaps[0] = startTime[0];
        for (int i = 1; i < n; i++) {
            gaps[i] = startTime[i] - endTime[i - 1];
        }
        gaps[n] = eventTime - endTime[n - 1];
        
        int originalMax = 0;
        for (int gap : gaps) {
            originalMax = Math.max(originalMax, gap);
        }
        
        int[] prefixMax = new int[n + 1];
        prefixMax[0] = gaps[0];
        for (int i = 1; i <= n; i++) {
            prefixMax[i] = Math.max(prefixMax[i - 1], gaps[i]);
        }
        
        int[] suffixMax = new int[n + 1];
        suffixMax[n] = gaps[n];
        for (int i = n - 1; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i + 1], gaps[i]);
        }
        
        int globalMax = originalMax;
        
        for (int i = 0; i < n; i++) {
            int duration = endTime[i] - startTime[i];
            int m = gaps[i] + duration + gaps[i + 1];
            
            int leftMax = (i > 0) ? prefixMax[i - 1] : 0;
            int rightMax = (i + 2 <= n) ? suffixMax[i + 2] : 0;
            int gOther = Math.max(leftMax, rightMax);
            
            int currentMaxCandidate = 0;
            boolean hasCandidate = false;
            
            if (m >= duration) {
                int candidate = Math.max(m - duration, gOther);
                if (candidate > currentMaxCandidate) {
                    currentMaxCandidate = candidate;
                    hasCandidate = true;
                }
            }
            if (gOther >= duration) {
                int candidate = Math.max(gOther - duration, m);
                if (candidate > currentMaxCandidate) {
                    currentMaxCandidate = candidate;
                    hasCandidate = true;
                }
            }
            
            if (hasCandidate && currentMaxCandidate > globalMax) {
                globalMax = currentMaxCandidate;
            }
        }
        
        return Math.max(originalMax, globalMax);
    }
}

JavaScript solution:
var maxFreeTime = function(eventTime, startTime, endTime) {
    const n = startTime.length;
    const originalGaps = [];
    originalGaps.push(startTime[0] - 0);
    for (let i = 1; i < n; i++) {
        originalGaps.push(startTime[i] - endTime[i - 1]);
    }
    originalGaps.push(eventTime - endTime[n - 1]);
    const m = originalGaps.length;
    const prefixMax = new Array(m).fill(0);
    prefixMax[0] = originalGaps[0];
    for (let i = 1; i < m; i++) {
        prefixMax[i] = Math.max(prefixMax[i - 1], originalGaps[i]);
    }
    const suffixMax = new Array(m).fill(0);
    suffixMax[m - 1] = originalGaps[m - 1];
    for (let i = m - 2; i >= 0; i--) {
        suffixMax[i] = Math.max(suffixMax[i + 1], originalGaps[i]);
    }
    let initialMax = Math.max(...originalGaps);
    let globalMax = initialMax;
    for (let i = 0; i < n; i++) {
        const s = startTime[i];
        const e = endTime[i];
        const d = e - s;
        let mergedGap;
        if (n === 1) {
            mergedGap = eventTime - 0;
        } else if (i === 0) {
            mergedGap = startTime[1] - 0;
        } else if (i === n - 1) {
            mergedGap = eventTime - endTime[i - 1];
        } else {
            mergedGap = startTime[i + 1] - endTime[i - 1];
        }
        const leftGapIndex = i;
        const rightGapIndex = i + 1;
        let maxLeft = 0;
        if (leftGapIndex > 0) {
            maxLeft = prefixMax[leftGapIndex - 1];
        }
        let maxRight = 0;
        if (rightGapIndex + 1 < m) {
            maxRight = suffixMax[rightGapIndex + 1];
        }
        const maxOtherGap = Math.max(maxLeft, maxRight);
        const otherPossible = maxOtherGap >= d;
        const mergedPossible = mergedGap >= d;
        if (!mergedPossible && !otherPossible) continue;
        let currentMax;
        if (otherPossible) {
            currentMax = mergedGap;
        } else {
            const newGap = mergedGap - d;
            currentMax = Math.max(newGap, maxOtherGap);
        }
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }
    return globalMax;
};

Python solution:
class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        if n == 0:
            return eventTime
        
        # Compute original free intervals' sizes
        pre_size = startTime[0] - 0
        mid_sizes = [startTime[i+1] - endTime[i] for i in range(n-1)]
        post_size = eventTime - endTime[-1]
        original_sizes = [pre_size] + mid_sizes + [post_size]
        
        # Precompute prefix and suffix max arrays
        m = len(original_sizes)
        prefix_max = [0] * m
        prefix_max[0] = original_sizes[0]
        for j in range(1, m):
            prefix_max[j] = max(prefix_max[j-1], original_sizes[j])
        
        suffix_max = [0] * m
        suffix_max[-1] = original_sizes[-1]
        for j in range(m-2, -1, -1):
            suffix_max[j] = max(suffix_max[j+1], original_sizes[j])
        
        original_max = max(original_sizes)
        max_candidate = 0
        
        for i in range(n):
            # Calculate S_size (merged interval after removing meeting i)
            if i > 0:
                prev_end = endTime[i-1]
            else:
                prev_end = 0
            if i < n-1:
                next_start = startTime[i+1]
            else:
                next_start = eventTime
            S_size = next_start - prev_end
            d = endTime[i] - startTime[i]
            
            # Determine max_remaining (max of original_sizes excluding i and i+1)
            if i == 0:
                if m >= 2:
                    max_remaining = suffix_max[2] if 2 < m else 0
                else:
                    max_remaining = 0
            elif i == n-1:
                max_remaining = prefix_max[n-2] if (n-2) >= 0 else 0
            else:
                left_part = prefix_max[i-1] if (i-1) >= 0 else 0
                right_part = suffix_max[i+2] if (i+2) < m else 0
                max_remaining = max(left_part, right_part)
            
            # Calculate options for inserting into S or max_remaining
            option1 = 0
            if S_size >= d:
                option1 = max(S_size - d, max_remaining)
            
            option2 = 0
            if max_remaining >= d:
                option2 = max(max_remaining - d, S_size)
            
            current_candidate = max(option1, option2)
            if current_candidate > max_candidate:
                max_candidate = current_candidate
        
        return max(original_max, max_candidate)

Ruby solution:
def max_free_time(event_time, start_time, end_time)
    return 0 if start_time.empty?

    # Compute gaps
    gaps = []
    gaps << start_time[0] - 0
    (1...start_time.size).each do |i|
        gaps << start_time[i] - end_time[i-1]
    end
    gaps << event_time - end_time[-1]

    initial_max_gap = gaps.max

    n = gaps.size - 1  # number of meetings is start_time.size, gaps.size is n+1

    # Precompute prefix_max and suffix_max
    prefix_max = Array.new(gaps.size, 0)
    prefix_max[0] = gaps[0]
    (1...gaps.size).each do |i|
        prefix_max[i] = [prefix_max[i-1], gaps[i]].max
    end

    suffix_max = Array.new(gaps.size, 0)
    suffix_max[-1] = gaps[-1]
    (gaps.size-2).downto(0) do |i|
        suffix_max[i] = [suffix_max[i+1], gaps[i]].max
    end

    max_candidate = 0

    start_time.each_with_index do |s, i|
        left_gap = gaps[i]
        right_gap = gaps[i+1]
        duration_i = end_time[i] - start_time[i]

        merged_gap = left_gap + right_gap + duration_i

        # Compute max_other_gap
        if i == 0
            left_part = 0
        else
            left_part = prefix_max[i-1]
        end

        if i + 2 >= gaps.size
            right_part = 0
        else
            right_part = suffix_max[i+2]
        end

        max_other_gap = [left_part, right_part].max

        # Compute option_a
        option_a = [merged_gap - duration_i, max_other_gap].max

        # Compute option_b
        if max_other_gap >= duration_i
            option_b_val = [merged_gap, max_other_gap - duration_i].max
            current_candidate = [option_a, option_b_val].max
        else
            current_candidate = option_a
        end

        max_candidate = current_candidate if current_candidate > max_candidate
    end

    [initial_max_gap, max_candidate].max
end