Reschedule Meetings for Maximum Free Time II

Medium

Asked by:

32 views

Topics:

ArraysTwo PointersSliding Windows

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 i^th 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.

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 <= 10⁹
n == startTime.length == endTime.length
2 <= n <= 10⁵
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

How are the meetings represented, and what are the data types for their start and end times? Are these integers representing minutes since the start of the day, or something else?
Are the meetings sorted, and if not, should I assume they are in a random order?
Can the meetings overlap, and if so, how should overlapping meetings be handled when calculating the maximum free time?
Is it possible for a meeting to start and end at the same time (i.e., a meeting with zero duration)? If so, how should this be treated?
What should be returned if there are no meetings scheduled? Should I assume the entire day is free, or is there a default return value to use in this edge case?

Brute Force Solution

Approach

The brute force approach to rescheduling meetings involves checking every possible combination of moving or canceling meetings. It's like trying every single option until we find the best one that maximizes the total free time available.

Here's how the algorithm would work step-by-step:

Consider all the meetings one by one.
For each meeting, think about two possibilities: either keep it as is, or reschedule it.
If rescheduling, consider ALL possible timeslots available within the given time frame for that meeting.
For each possible combination of keeping or rescheduling each of the meetings, calculate the total free time.
After checking EVERY single combination of meeting schedules, compare the total free time for each combination.
Finally, pick the schedule that gives you the maximum total free time, which is the best solution.

Code Implementation

def reschedule_meetings_brute_force(meetings, available_time_start, available_time_end):

    maximum_free_time = 0
    
    def calculate_free_time(scheduled_meetings):
        scheduled_meetings.sort()
        total_free_time = 0
        last_meeting_end = available_time_start
        
        for meeting_start, meeting_end in scheduled_meetings:
            total_free_time += max(0, meeting_start - last_meeting_end)
            last_meeting_end = max(last_meeting_end, meeting_end)
        
        total_free_time += max(0, available_time_end - last_meeting_end)
        return total_free_time

    def generate_combinations(index, current_schedule):
        nonlocal maximum_free_time

        if index == len(meetings):
            # Base case: all meetings considered
            free_time = calculate_free_time(current_schedule)
            maximum_free_time = max(maximum_free_time, free_time)
            return

        meeting_start_time, meeting_end_time = meetings[index]

        # Option 1: Keep the meeting as is
        generate_combinations(index + 1, current_schedule + [(meeting_start_time, meeting_end_time)])

        # Option 2: Reschedule or cancel the meeting
        meeting_duration = meeting_end_time - meeting_start_time
        for reschedule_start_time in range(available_time_start, available_time_end - meeting_duration + 1):
            reschedule_end_time = reschedule_start_time + meeting_duration
            #Check if the rescheduled time does not exceed the upper bound
            if reschedule_end_time <= available_time_end:
                generate_combinations(index + 1, current_schedule + [(reschedule_start_time, reschedule_end_time)])

        # Option 3: Cancel the meeting
        generate_combinations(index + 1, current_schedule)

    # Start the recursive process to explore all combinations.
    generate_combinations(0, [])

    return maximum_free_time

Big(O) Analysis

Time Complexity

O(m^n) – The brute force approach considers each of the n meetings and explores all possible rescheduling options. For each meeting, we have two choices: keep it or reschedule it. If rescheduling, we need to consider m possible timeslots. Thus, in the worst case, each of the n meetings can be rescheduled to each of the m timeslots, leading to m options for each of the n meetings. The number of possible schedules is m multiplied by itself n times, or m^n. Therefore, the time complexity is O(m^n).

Space Complexity

O(2^N * K) – The brute force approach considers all possible combinations of keeping or rescheduling meetings. For N meetings, this results in 2^N possible schedules. For each of these schedules, the algorithm needs to consider all possible rescheduling options. In the worst-case scenario, for each meeting being rescheduled, the algorithms may need to consider K timeslots if there are K possible slots. Thus, we need to store a schedule of size N, and for each combination we can potentially store K reschedules. Consequently, the space complexity is dominated by the need to enumerate and partially store each of the 2^N meeting schedules which, on rescheduling of a meeting, requires storing K alternative schedule times. After checking all combinations we store the maximum free time to compare, resulting in O(2^N * K) auxiliary space complexity.

Optimal Solution

Approach

We want to find the largest possible chunk of free time by rescheduling meetings. The smart way to do this involves merging overlapping meetings to simplify the schedule and then figuring out the biggest gap in the new, combined schedule.

Here's how the algorithm would work step-by-step:

First, take all the meetings and combine any that overlap with each other into bigger, single meetings. Think of it as simplifying the calendar by getting rid of all the little conflicts.
Once you have a list of non-overlapping meetings, sort them by their start times to put them in chronological order. This helps us easily see what's happening on the schedule from start to finish.
Now, walk through the sorted meetings and calculate the free time between each meeting. This is simply the time between the end of one meeting and the start of the next.
Keep track of the biggest gap you find between any two meetings. This largest gap is the maximum amount of free time we can achieve by rescheduling things optimally.
Finally, return this maximum free time.

Code Implementation

def find_max_free_time(meetings):
    merged_meetings = merge_overlapping_meetings(meetings)

    sorted_meetings = sorted(merged_meetings, key=lambda meeting: meeting[0])

    max_free_time = calculate_max_free_time(sorted_meetings)

    return max_free_time

def merge_overlapping_meetings(meetings):
    meetings.sort(key=lambda x: x[0])
    merged_meetings = []

    for meeting in meetings:
        if not merged_meetings or meeting[0] > merged_meetings[-1][1]:
            merged_meetings.append(meeting)
        else:
            merged_meetings[-1] = [merged_meetings[-1][0], max(merged_meetings[-1][1], meeting[1])]
    return merged_meetings

def calculate_max_free_time(sorted_meetings):
    max_free_time = 0

    # Find the longest gap between meetings.
    for i in range(len(sorted_meetings) - 1):
        free_time_between_meetings = sorted_meetings[i+1][0] - sorted_meetings[i][1]
        max_free_time = max(max_free_time, free_time_between_meetings)

    # Account for the possibility of no free time at all.
    return max_free_time

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operations are merging overlapping intervals, sorting the merged intervals, and then finding the largest gap. Merging overlapping intervals involves iterating through the n meetings, potentially requiring comparisons with other meetings (though efficient implementations can do it in O(n) overall). Sorting the n merged intervals takes O(n log n) time. Iterating through the sorted list to find the maximum gap takes O(n) time. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The primary space complexity comes from the need to merge overlapping meetings. In the worst-case scenario, where no meetings overlap, we create a new list of size N to store these non-overlapping meetings, where N is the initial number of meetings. Sorting the merged meetings may also require auxiliary space depending on the sorting algorithm used; in the worst-case scenario using an algorithm like merge sort or quicksort, it will use O(N) space. The remaining operations only involve iterating through the sorted meetings and keeping track of a maximum value, which requires constant space.

Edge Cases

Case	How to Handle
Meetings is null or empty	Return 0 (or appropriate minimum free time value) immediately since there are no meetings to reschedule.
Meetings array contains single meeting	Return the length of the single meeting interval as the total occupied time.
Meetings array contains meeting intervals with same start and end times (zero-length meetings)	Treat them as valid meetings but contributing zero length, ensuring calculations are still correct by considering valid cases.
Meetings array contains overlapping meeting intervals	The algorithm must correctly merge or consolidate overlapping intervals to calculate the total occupied time efficiently.
Meetings array contains meeting intervals that are adjacent (e.g. [1,2], [2,3])	The algorithm needs to decide whether to merge these into one large interval or keep them separated.
Extremely large meeting intervals that might cause Integer overflow when calculating durations	Consider using long data type to avoid integer overflow in duration calculations.
Meetings array has a very large number of meeting intervals. (Performance consideration)	Ensure the algorithm's time complexity remains acceptable (ideally O(n log n) or O(n) if possible) by choosing efficient data structures and algorithms.
Meetings array is already sorted	The algorithm needs to handle the sorted input without significantly impacting performance, or skip redundant sort operations if sorting is used.

Meetings is null or empty

How to Handle:

Return 0 (or appropriate minimum free time value) immediately since there are no meetings to reschedule.

Meetings array contains single meeting

How to Handle:

Return the length of the single meeting interval as the total occupied time.

Meetings array contains meeting intervals with same start and end times (zero-length meetings)

How to Handle:

Treat them as valid meetings but contributing zero length, ensuring calculations are still correct by considering valid cases.

Meetings array contains overlapping meeting intervals

How to Handle:

The algorithm must correctly merge or consolidate overlapping intervals to calculate the total occupied time efficiently.

Meetings array contains meeting intervals that are adjacent (e.g. [1,2], [2,3])

How to Handle:

The algorithm needs to decide whether to merge these into one large interval or keep them separated.

Extremely large meeting intervals that might cause Integer overflow when calculating durations

How to Handle:

Consider using long data type to avoid integer overflow in duration calculations.

Meetings array has a very large number of meeting intervals. (Performance consideration)

How to Handle:

Ensure the algorithm's time complexity remains acceptable (ideally O(n log n) or O(n) if possible) by choosing efficient data structures and algorithms.

Meetings array is already sorted

How to Handle:

The algorithm needs to handle the sorted input without significantly impacting performance, or skip redundant sort operations if sorting is used.