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 I

Number: 3743

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given an event that spans from time t = 0 to t = eventTime. There are n non‐overlapping meetings given by their startTime and endTime. You are allowed to reschedule (that is, shift the start time of) at most k of these meetings while keeping each meeting’s duration unchanged; the relative order of the meetings must remain the same and meetings must continue to be non overlapping as well as remain completely in the range [0, eventTime]. The goal is to maximize the length of the longest continuous free (unoccupied) period during the event after performing at most k reschedulings.

For example, in one test case with eventTime = 5, k = 1, startTime = [1,3] and endTime = [2,5], one optimal solution is to reschedule the meeting originally at [1,2] to [2,3] so that the free period from time 0 to 2 has length 2.

Key Insights

  • The meetings come in sorted order and do not overlap. Rescheduling up to k meetings gives us the power to “clear out” a portion of the timeline.
  • Once a meeting is chosen not to be moved (fixed), its start and end times remain; all other (rescheduled) meetings can be placed arbitrarily (subject to order and event boundaries). Thus one may “carve out” a free gap between two meetings that remain fixed.
  • There are three kinds of candidate free gaps: • A gap at the beginning of the event—if some prefix meetings are rescheduled to occur at the very start. • A gap at the end—if some suffix meetings are rescheduled to be as late as possible. • A gap in the middle between two fixed meetings (with some meetings between them having been rescheduled away from this gap).
  • A common strategy is to “guess” a candidate free gap length L (via binary search) and then design a greedy algorithm that verifies whether one can “clear” an interval of length L by assigning rescheduled meetings to “one side” of that interval. The verification uses the fact that by not moving some meetings (making them “fixed”), the free interval is forced to lie either before the first fixed meeting, after the last fixed meeting, or between two fixed meetings.
  • In the feasibility check for a candidate L one implicitly does the following: • For the left‐side free gap, one “compresses” all meetings that occur before the gap as early as possible so that their total lengths are “packed” at the beginning. • Similarly, for a gap in the middle one chooses two fixed meetings and “pushes” all meetings that are allowed to be rescheduled “away” from the gap.
  • Thus the algorithm is a combination of binary search (over L) and a greedy/dynamic–programming feasibility routine.

Space and Time Complexity

Time Complexity: O(n log(eventTime))
Space Complexity: O(1) (ignoring input storage)

Solution

The high-level idea is to use binary search on the answer. For a candidate free time L we check if there is some way to “reassign” (i.e. reschedule) at most k meetings so that a gap of length L appears somewhere in the event.

To do so we consider three cases:

  1. Clearing a gap at the beginning: We try to “compress” all meetings before a certain index to the very start. In effect, if the total durations of the meetings that we must move are small enough, it is possible to “push” the first fixed meeting farther to the right so that the free gap before it becomes at least L.
  2. Clearing a gap at the end: Similarly, we “compress” the meetings after the last fixed meeting to the very end.
  3. Clearing a gap between two fixed meetings: Here we choose two meetings that we will leave untouched and “push” intervening (rescheduled) meetings completely away from the interval between the fixed ones. The available free gap is then the original gap between the fixed meeting end and the next fixed meeting start. In each case the number of meetings that you decide to “shift” must not exceed k. Because the meeting durations are fixed, if you know the total “space” taken by meetings being forced to one side, you can compute how far the fixed meeting can be shifted (only within the event boundaries). The binary search feasibility function simulates these ideas: it “sweeps” through the meeting list (or considers possible fixed‐meeting pairs) and checks if a gap of length L can be achieved with at most k reschedulings.

Once the feasibility check is written, standard binary search (over L from 0 to eventTime) finds the maximum possible free gap.

Below, sample code solutions are given in Python, JavaScript, C++, and Java. In the solutions, clear variable names and inline comments explain each step.

Code Solutions

# Python solution with inline comments
def maxFreeTime(eventTime, k, startTime, endTime):
    n = len(startTime)
    
    # Helper: Given candidate free gap L, check if it is possible
    # to achieve a free interval of length L by rescheduling at most k meetings.
    def can_achieve(L):
        # Case 1: Free gap at beginning.
        # We want to push as many meetings as necessary to the left.
        sum_duration = 0
        # Find the smallest index j such that the fixed meeting at j has startTime >= L + total duration of meetings before j.
        for j in range(n):
            # If we choose to reschedule meetings from 0 to j-1,
            # they can be “packed” at time 0 and take sum_duration time.
            # Then meeting j remains fixed and will still start at startTime[j].
            if startTime[j] - sum_duration >= L:
                # The number of meetings we rescheduled = j.
                if j <= k:
                    return True
            # Accumulate meeting j's duration (if we decide to reschedule it instead)
            sum_duration += endTime[j] - startTime[j]
        # Case 2: Free gap at the end.
        sum_duration = 0
        for j in range(n - 1, -1, -1):
            if eventTime - endTime[j] - sum_duration >= L:
                # rescheduled meetings count = (n - 1 - j)
                if (n - 1 - j) <= k:
                    return True
            sum_duration += endTime[j] - startTime[j]
        
        # Case 3: Free gap in the middle.
        # Try every possible pair of fixed meetings i and j with i < j.
        # When choosing i and j as boundaries (which we do not move), 
        # all meetings strictly between them (i+1...j-1) are rescheduled.
        i = 0
        # Use two pointers to ensure that the cost (j-i-1) does not exceed k.
        for j in range(1, n):
            # While the number of meetings between i and j is too high, move i forward.
            while j - i - 1 > k:
                i += 1
            # With meetings between i and j removed, free gap is interval between endTime[i] and startTime[j].
            if startTime[j] - endTime[i] >= L:
                return True
        return False

    # Binary search for maximum free gap possible
    lo, hi = 0, eventTime
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_achieve(mid):
            ans = mid
            lo = mid + 1  # try for a larger gap
        else:
            hi = mid - 1
    return ans

# Example usage
print(maxFreeTime(5, 1, [1, 3], [2, 5]))   # Expected output: 2
print(maxFreeTime(10, 1, [0, 2, 9], [1, 4, 10]))   # Expected output: 6
← Back to All Questions