☣︎ Beginner-Friendly Guide: “Reschedule Meetings for Maximum Free Time II” – LeetCode 3440 (C++ | Python | JavaScript)

Posted on by — No Comments ↓

In real-world scheduling scenarios, there’s often flexibility in meeting times. LeetCode 3440 explores a variation where you’re allowed to reschedule one meeting to potentially maximize your continuous free time during a larger event. Unlike its predecessor, the relative order of meetings can now be changed. This introduces an interesting optimization problem that mixes greedy scanning with intelligent rescheduling.

🧠 Problem Summary

You are given:

  • An integer eventTime, representing the full span of the event (from t = 0 to t = eventTime).
  • Two arrays: startTime[] and endTime[], where each pair defines the start and end times of n non-overlapping meetings.

You can reschedule at most one meeting (by changing its start time but keeping its duration the same), as long as:

  • The new time doesn’t exceed event bounds.
  • Meetings stay non-overlapping.

Goal: Maximize the longest continuous free time after such rescheduling.

🔧 Intuition

The main idea is to:

  1. Traverse from left to right, tracking the largest gap before each meeting.
  2. Traverse from right to left, tracking the largest gap after each meeting.
  3. At each step, determine the maximum free block achievable by shifting a meeting into a known gap.

The meeting durations stay fixed. By checking if we can fit a meeting into a larger previous or subsequent gap, we determine the best possible outcome.

💪 C++ Code

#include <ranges>

class Solution {
public:
  int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
    int n = startTime.size();
    int max_gap_before = 0;
    int last_end = 0;
    int max_free_time = 0;

    for (int i = 0; i < n; ++i) {
      int meeting_time = endTime[i] - startTime[i];
      int next_start = (i == n - 1) ? eventTime : startTime[i + 1];
      int free_time = next_start - last_end;
      if (meeting_time > max_gap_before) free_time -= meeting_time;
      max_free_time = max(max_free_time, free_time);
      max_gap_before = max(max_gap_before, startTime[i] - last_end);
      last_end = endTime[i];
    }

    int max_gap_after = 0;
    int last_start = eventTime;
    for (int i = n - 1; i >= 0; --i) {
      int meeting_time = endTime[i] - startTime[i];
      int prev_end = (i == 0) ? 0 : endTime[i - 1];
      int free_time = last_start - prev_end;
      if (meeting_time <= max_gap_after)
        max_free_time = max(max_free_time, free_time);
      max_gap_after = max(max_gap_after, last_start - endTime[i]);
      last_start = startTime[i];
    }

    return max_free_time;
  }
};

🐍 Python Code

class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        max_gap_before, max_free_time, last_end = 0, 0, 0

        for i in range(n):
            meeting_time = endTime[i] - startTime[i]
            next_start = eventTime if i == n - 1 else startTime[i + 1]
            free_time = next_start - last_end
            if meeting_time > max_gap_before:
                free_time -= meeting_time
            max_free_time = max(max_free_time, free_time)
            max_gap_before = max(max_gap_before, startTime[i] - last_end)
            last_end = endTime[i]

        max_gap_after, last_start = 0, eventTime
        for i in reversed(range(n)):
            meeting_time = endTime[i] - startTime[i]
            prev_end = 0 if i == 0 else endTime[i - 1]
            free_time = last_start - prev_end
            if meeting_time <= max_gap_after:
                max_free_time = max(max_free_time, free_time)
            max_gap_after = max(max_gap_after, last_start - endTime[i])
            last_start = startTime[i]

        return max_free_time

🔌 JavaScript Code

var maxFreeTime = function(eventTime, startTime, endTime) {
    let n = startTime.length;
    let maxGapBefore = 0, maxFreeTime = 0, lastEnd = 0;

    for (let i = 0; i < n; i++) {
        let duration = endTime[i] - startTime[i];
        let nextStart = (i === n - 1) ? eventTime : startTime[i + 1];
        let freeTime = nextStart - lastEnd;
        if (duration > maxGapBefore) freeTime -= duration;
        maxFreeTime = Math.max(maxFreeTime, freeTime);
        maxGapBefore = Math.max(maxGapBefore, startTime[i] - lastEnd);
        lastEnd = endTime[i];
    }

    let maxGapAfter = 0, lastStart = eventTime;
    for (let i = n - 1; i >= 0; i--) {
        let duration = endTime[i] - startTime[i];
        let prevEnd = (i === 0) ? 0 : endTime[i - 1];
        let freeTime = lastStart - prevEnd;
        if (duration <= maxGapAfter)
            maxFreeTime = Math.max(maxFreeTime, freeTime);
        maxGapAfter = Math.max(maxGapAfter, lastStart - endTime[i]);
        lastStart = startTime[i];
    }

    return maxFreeTime;
};

📝 Key Takeaways

  • Forward and reverse traversal helps us identify optimal gaps.
  • Keep track of the largest gaps before and after each position.
  • The ability to break order adds complexity but increases optimization potential.
  • Avoid brute force. This solution runs in O(n) with no heap or segment trees.

✅ Final Thoughts

This variant of the rescheduling problem showcases the power of greedy planning and gap analysis. Real-life calendar apps, conference schedulers, or even logistics timelines could benefit from such logic. It’s not always about cramming more into the schedule — sometimes it’s about creating meaningful free time.

Let this pattern guide your approach in future scheduling problems!

Leave a Reply