Reschedule meetings for maximum free time ii

Array Greedy Enumeration

60.4% acceptance

Feb 25, 2026

465

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_free_time(event_time: i32, start_time: Vec<i32>, end_time: Vec<i32>) -> i32 {
    let n = start_time.len();
    // gaps[0] = start_time[0], gaps[i] = start_time[i] - end_time[i-1], gaps[n] = event_time - end_time[n-1]
    let mut gaps = vec![0i32; n + 1];
    gaps[0] = start_time[0];
    for i in 1..n { gaps[i] = start_time[i] - end_time[i-1]; }
    gaps[n] = event_time - end_time[n-1];
    // duration of meeting i = end_time[i] - start_time[i]
    let dur: Vec<i32> = (0..n).map(|i| end_time[i] - start_time[i]).collect();
    let mut ans = *gaps.iter().max().unwrap();
    // Try removing each meeting: merged free = gaps[i] + dur[i] + gaps[i+1]
    // But then we also need to check if we can insert dur[i] into some other gap
    // For version II (can reorder), if dur[i] <= max_gap_excluding_adjacent, we get
    // gaps[i] + dur[i] + gaps[i+1], else gaps[i] + gaps[i+1]
    // Precompute prefix/suffix max gaps
    let mut prefix_max = vec![0i32; n + 2];
    let mut suffix_max = vec![0i32; n + 2];
    for i in 0..=n { prefix_max[i+1] = prefix_max[i].max(gaps[i]); }
    for i in (0..=n).rev() { suffix_max[i] = suffix_max[i+1].max(gaps[i]); }
    for i in 0..n {
      let merged = gaps[i] + dur[i] + gaps[i+1];
      // Max gap excluding gaps[i] and gaps[i+1]
      let max_other = if i >= 1 { prefix_max[i] } else { 0 }.max(if i+2 <= n { suffix_max[i+2] } else { 0 });
      let free = if dur[i] <= max_other { merged } else { gaps[i] + gaps[i+1] };
      ans = ans.max(free);
    }
    ans
  }
}