We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reschedule Meetings for Maximum Free Time II

Difficulty: Medium

Problem Description

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

Key Insights

  • Meetings are non-overlapping and can be rescheduled while maintaining their duration.
  • We need to identify gaps between meetings to find potential free time.
  • The goal is to maximize the longest continuous free time after rescheduling one meeting.
  • The relative order of meetings can change after rescheduling one meeting.

Space and Time Complexity

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

Solution

The solution involves determining the gaps between the scheduled meetings and calculating the maximum free time possible after rescheduling one meeting. We can iterate through the given start and end times to find free intervals. The main steps are:

  1. Calculate the initial free time based on the existing meeting schedule.
  2. For each meeting, consider rescheduling it to the end of the previous meeting or the start of the next meeting, if possible.
  3. Update the free time accordingly and keep track of the maximum free time achieved.

This approach primarily uses an array to store the start and end times and iterates through them, maintaining a running maximum of free time.

Code Solutions

def maxFreeTime(eventTime, startTime, endTime):
    n = len(startTime)
    free_time = 0
    max_free_time = 0
    
    # Calculate initial free time between meetings
    for i in range(1, n):
        free_time += startTime[i] - endTime[i - 1]

    # Check the maximum free time without rescheduling
    max_free_time = free_time

    # Try to reschedule each meeting
    for i in range(n):
        meeting_duration = endTime[i] - startTime[i]
        
        # Reschedule to the end of the previous meeting
        if i > 0:
            new_start = endTime[i - 1]
            new_end = new_start + meeting_duration
            if new_end <= startTime[i]:
                # Calculate new free time
                new_free_time = free_time - (startTime[i] - endTime[i - 1]) + (startTime[i] - new_end)
                max_free_time = max(max_free_time, new_free_time)

        # Reschedule to the start of the next meeting
        if i < n - 1:
            new_start = startTime[i + 1] - meeting_duration
            new_end = startTime[i + 1]
            if new_start >= 0:
                # Calculate new free time
                new_free_time = free_time - (startTime[i + 1] - endTime[i]) + (startTime[i + 1] - new_start)
                max_free_time = max(max_free_time, new_free_time)

    return max_free_time
← Back to All Questions