3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution

In this guide, you will get 3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution with the best time and space complexity. The solution to Reschedule Meetings for Maximum Free Time II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Reschedule Meetings for Maximum Free Time II solution in C++
  4. Reschedule Meetings for Maximum Free Time II solution in Java
  5. Reschedule Meetings for Maximum Free Time II solution in Python
  6. Additional Resources
3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution image

Problem Statement of Reschedule Meetings for Maximum Free Time II

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.

See also  1604. Alert Using Same Key-Card Three or More Times in a One Hour Period LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution in C++

class Solution {
 public:
  int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
    const int n = startTime.size();
    const vector<int> gaps = getGaps(eventTime, startTime, endTime);
    int ans = 0;
    vector<int> maxLeft(n + 1);   // maxLeft[i] := max(gaps[0..i])
    vector<int> maxRight(n + 1);  // maxRight[i] := max(gaps[i..n])

    maxLeft[0] = gaps[0];
    maxRight[n] = gaps[n];

    for (int i = 1; i < n + 1; ++i)
      maxLeft[i] = max(gaps[i], maxLeft[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      maxRight[i] = max(gaps[i], maxRight[i + 1]);

    for (int i = 0; i < n; ++i) {
      const int currMeetingTime = endTime[i] - startTime[i];
      const int adjacentGapsSum = gaps[i] + gaps[i + 1];
      const bool canMoveMeeting =
          currMeetingTime <= max(i > 0 ? maxLeft[i - 1] : 0,  //
                                 i + 2 < n + 1 ? maxRight[i + 2] : 0);
      ans = max(ans, adjacentGapsSum + (canMoveMeeting ? currMeetingTime : 0));
    }

    return ans;
  }

 private:
  vector<int> getGaps(int eventTime, const vector<int>& startTime,
                      const vector<int>& endTime) {
    vector<int> gaps{startTime[0]};
    for (int i = 1; i < startTime.size(); ++i)
      gaps.push_back(startTime[i] - endTime[i - 1]);
    gaps.push_back(eventTime - endTime.back());
    return gaps;
  }
};
/* code provided by PROGIEZ */

3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution in Java

class Solution {
  public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
    final int n = startTime.length;
    final int[] gaps = getGaps(eventTime, startTime, endTime);
    int ans = 0;
    int[] maxLeft = new int[n + 1];  // maxLeft[i] := max(gaps[0..i])
    int[] maxRight = new int[n + 1]; // maxRight[i] := max(gaps[i..n])

    maxLeft[0] = gaps[0];
    maxRight[n] = gaps[n];

    for (int i = 1; i < n + 1; ++i)
      maxLeft[i] = Math.max(gaps[i], maxLeft[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      maxRight[i] = Math.max(gaps[i], maxRight[i + 1]);

    for (int i = 0; i < n; ++i) {
      final int currMeetingTime = endTime[i] - startTime[i];
      final int adjacentGapsSum = gaps[i] + gaps[i + 1];
      final boolean canMoveMeeting =
          currMeetingTime <= Math.max(i > 0 ? maxLeft[i - 1] : 0, //
                                      i + 2 < n + 1 ? maxRight[i + 2] : 0);
      ans = Math.max(ans, adjacentGapsSum + (canMoveMeeting ? currMeetingTime : 0));
    }

    return ans;
  }

  private int[] getGaps(int eventTime, int[] startTime, int[] endTime) {
    int[] gaps = new int[startTime.length + 1];
    gaps[0] = startTime[0];
    for (int i = 1; i < startTime.length; ++i)
      gaps[i] = startTime[i] - endTime[i - 1];
    gaps[startTime.length] = eventTime - endTime[endTime.length - 1];
    return gaps;
  }
}
// code provided by PROGIEZ

3440. Reschedule Meetings for Maximum Free Time II LeetCode Solution in Python

class Solution:
  def maxFreeTime(
      self,
      eventTime: int,
      startTime: list[int],
      endTime: list[int]
  ) -> int:
    n = len(startTime)
    gaps = ([startTime[0]] +
            [startTime[i] - endTime[i - 1] for i in range(1, len(startTime))] +
            [eventTime - endTime[-1]])
    ans = 0
    maxLeft = [gaps[0]] + [0] * n  # maxLeft[i] := max(gaps[0..i])
    maxRight = [0] * n + [gaps[n]]  # maxRight[i] := max(gaps[i..n])

    for i in range(1, n + 1):
      maxLeft[i] = max(gaps[i], maxLeft[i - 1])

    for i in range(n - 1, -1, -1):
      maxRight[i] = max(gaps[i], maxRight[i + 1])

    for i, (start, end) in enumerate(zip(startTime, endTime)):
      currMeetingTime = end - start
      adjacentGapsSum = gaps[i] + gaps[i + 1]
      canMoveMeeting = currMeetingTime <= max(
          maxLeft[i - 1] if i > 0 else 0,
          maxRight[i + 2] if i + 2 < n + 1 else 0
      )
      ans = max(ans, adjacentGapsSum +
                (currMeetingTime if canMoveMeeting else 0))

    return ans
# code by PROGIEZ

Additional Resources

See also  6. Zigzag Conversion LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.