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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reschedule Meetings for Maximum Free Time II

Number: 3741

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given the total duration of an event (eventTime) and n non‐overlapping meetings represented by their start and end times. You are allowed to reschedule at most one meeting; that is, you can move its start (keeping its duration the same) as long as all meetings remain non-overlapping and within the event’s time window. The relative order of meetings may change after rescheduling. The goal is to maximize the longest continuous free time (i.e. a time interval during which no meeting occurs) during the event after moving at most one meeting.

Key Insights

  • The event timeline is initially occupied by fixed meetings that leave “free gaps” at the beginning, between meetings, and at the end.
  • Without any move, the maximum free time is the largest of these gaps.
  • Rescheduling one meeting effectively “removes” it from its current position, thereby merging its two adjacent free intervals (if it is in the middle) into one larger free interval.
  • However, we must place the moved meeting into some other free gap. Thus, we can only perform the reschedule if there exists a free gap (from the original schedule) that is large enough to host the meeting (its duration).
  • For each meeting, if removed, the potentially merged free time is: • For the first meeting: from t = 0 to start time of the second meeting. • For the last meeting: from the end time of the second-to-last meeting to eventTime. • For an interior meeting: from the end time of its previous meeting to the start time of its next meeting.
  • Finally, the answer is the maximum free time we can achieve either by not moving any meeting or by removing one meeting (subject to the feasibility of re-placing it in an existing free gap).

Space and Time Complexity

Time Complexity: O(n), where n is the number of meetings, because we compute free gaps and check each meeting in one pass. Space Complexity: O(1) (aside from input storage) since we only use a fixed number of extra variables.

Solution

The solution works in two parts:

  1. Precompute the maximum free gap available from the original schedule. The free gaps are:

    • From time 0 to the start of the first meeting.
    • Between consecutive meetings (the gap from the end of meeting j to the start of meeting j+1).
    • From the end of the last meeting to eventTime. This maximum gap represents the largest segment where a meeting can be relocated without overlap.

  2. For each meeting, consider “removing” it from its current position. The gap that forms by removal is:

    • If it is the first meeting: free time = start time of the second meeting − 0.
    • If it is the last meeting: free time = eventTime − end time of the second-to-last meeting.
    • Otherwise: free time = (start time of the next meeting) − (end time of the previous meeting). This gap is only valid if there is an available free gap (from step 1) that can accommodate the meeting’s duration (i.e. the meeting can be relocated). The meeting’s duration is (endTime[i] − startTime[i]).

Finally, the final answer is the maximum value between the original maximum free gap and all valid gaps obtained by “removing” each possible meeting.

Code Solutions

Below are code implementations with line-by-line comments in Python, JavaScript, C++, and Java.

# Python solution
def maxFreeTime(eventTime, startTime, endTime):
    n = len(startTime)
    
    # Calculate the maximum available free gap in the original schedule.
    max_available_gap = 0
    # Gap before the first meeting
    max_available_gap = max(max_available_gap, startTime[0] - 0)
    # Gaps between meetings
    for j in range(n - 1):
        gap = startTime[j + 1] - endTime[j]
        max_available_gap = max(max_available_gap, gap)
    # Gap after the last meeting
    max_available_gap = max(max_available_gap, eventTime - endTime[-1])
    
    # Initialize answer with the original maximum free gap
    answer = max_available_gap
    
    # Consider each meeting to remove (reschedule)
    for i in range(n):
        meeting_duration = endTime[i] - startTime[i]
        # Check if we can relocate the meeting using an available gap:
        # We need a gap that is at least as long as the meeting duration.
        if max_available_gap < meeting_duration:
            continue  # Not possible to move this meeting
        
        # Calculate the free period if meeting i is removed
        if i == 0:
            # If first meeting, free interval: from time 0 to the start of the second meeting
            if n >= 2:
                candidate_gap = startTime[1] - 0
            else:
                candidate_gap = eventTime
        elif i == n - 1:
            # If last meeting, free interval: from end of second-to-last meeting to eventTime
            candidate_gap = eventTime - endTime[i - 1]
        else:
            # For a meeting in the middle, free interval is from the end of the previous meeting to the start of the next meeting
            candidate_gap = startTime[i + 1] - endTime[i - 1]
        
        # Update the answer with the maximum possible free time
        answer = max(answer, candidate_gap)
    
    return answer

# Example usage:
eventTime = 10
startTime = [0,7,9]
endTime = [1,8,10]
print(maxFreeTime(eventTime, startTime, endTime))  # Output: 7
← Back to All Questions