Reschedule Meetings for Maximum Free Time I

Medium

Asked by:

14 views

Topics:

ArraysSliding WindowsGreedy Algorithms

You are given an integer eventTime denoting the duration of an event, where the event occurs from time t = 0 to time t = eventTime.

You are also given two integer arrays startTime and endTime, each of length n. These represent the start and end time of n non-overlapping meetings, where the i^th meeting occurs during the time [startTime[i], endTime[i]].

You can reschedule at most k meetings by moving their start time while maintaining the same duration, to maximize the longest continuous period of free time during the event.

The relative order of all the meetings should stay the same and they should remain non-overlapping.

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.

Example 1:

Input: eventTime = 5, k = 1, 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, k = 1, startTime = [0,2,9], endTime = [1,4,10]

Output: 6

Explanation:

Reschedule the meeting at [2, 4] to [1, 3], leaving no meetings during the time [3, 9].

Example 3:

Input: eventTime = 5, k = 2, 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⁵
1 <= k <= n
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:

What is the format of the meeting intervals (e.g., start and end times as integers, strings, or date objects)? And what units do these times represent?
Are the meeting intervals guaranteed to be sorted, or do I need to sort them first?
Can meeting intervals overlap? If so, how should I handle overlapping intervals when calculating free time?
What should I return if there are no meetings scheduled at all, or if the provided meeting schedule is empty?
What is the expected output format for the maximum free time? Is it a single number (duration) or another meeting interval (start and end)? What data type should the return value have?

Brute Force Solution

Approach

The brute force strategy involves trying every possible combination of rescheduling one meeting. For each potential schedule, we calculate the amount of free time and pick the schedule that gives us the most free time.

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

First, consider rescheduling each meeting one at a time.
For each meeting, try moving it to every possible available time slot.
For each of these new potential schedules, calculate the total amount of free time available.
Compare the free time of each rescheduled meeting schedule to the original schedule.
Choose the rescheduled meeting schedule that results in the greatest amount of free time.

Code Implementation

def reschedule_meetings_brute_force(meetings):    best_schedule = meetings
    max_free_time = calculate_free_time(meetings)

    for meeting_index in range(len(meetings)):

        original_meeting = meetings[meeting_index]

        # Iterate through possible start times
        for new_start_time in range(0, 24):
            
            # Create a temporary meeting schedule.
            temp_meetings = meetings[:]

            # Attempt to reschedule current meeting.
            temp_meeting = (new_start_time, new_start_time + (original_meeting[1] - original_meeting[0]))
            temp_meetings[meeting_index] = temp_meeting

            # Calculate free time to check the schedule.
            current_free_time = calculate_free_time(temp_meetings)

            # Find the schedule with the maximum free time
            if current_free_time > max_free_time:

                # Update max free time and save the new schedule.
                max_free_time = current_free_time
                best_schedule = temp_meetings[:]

    return best_schedule

def calculate_free_time(meetings):
    meetings.sort()
    total_free_time = 0
    end_time = 0

    for meeting in meetings:
        start_time = meeting[0]
        meeting_end_time = meeting[1]

        # Calculate gaps between meetings.
        if start_time > end_time:
            total_free_time += start_time - end_time

        end_time = max(end_time, meeting_end_time)

    total_free_time += (24 - end_time)

    return total_free_time

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each of the n meetings. For each meeting, it tries to reschedule it to potentially every possible time slot. Assuming there are n potential time slots (in the worst case, as many time slots as meetings), this gives a factor of n. Then, for each of these rescheduled schedules, it calculates the total free time, which involves iterating through all the meetings again to identify conflicts and calculate free time, adding another factor of n. Therefore, the overall time complexity is O(n * n * n) = O(n^3).

Space Complexity

O(1) – The described brute force strategy primarily involves iterating and comparing free time values. While we recalculate free time for each potential schedule, the calculation itself seems to use only a few variables to store temporary results and the maximum free time found so far. The number of these variables does not depend on the number of meetings or the size of the schedule, which we can represent as N. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

To maximize free time, we need to find the biggest gap between meetings. First, sort the meetings by start time. Then, calculate the duration of the gaps between consecutive meetings.

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

Arrange all the meetings in order of when they begin.
Look at the time between each meeting and the meeting that comes right after it. This gives you the free time slots.
Find the biggest free time slot. This is the maximum free time you can have.

Code Implementation

def find_max_free_time(meetings):
    # Sort the meetings by start time to easily find gaps.
    meetings.sort(key=lambda meeting: meeting[0])

    max_free_time = 0
    # Iterate through meetings to find the largest gap.
    for i in range(1, len(meetings)):
        previous_meeting_end = meetings[i - 1][1]
        current_meeting_start = meetings[i][0]

        # Calculate the gap between consecutive meetings.
        free_time_duration = current_meeting_start - previous_meeting_end
        
        # Update max_free_time if the current gap is larger.
        max_free_time = max(max_free_time, free_time_duration)

    return max_free_time

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the meetings by start time. Sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n), where n is the number of meetings. After sorting, iterating through the sorted meetings to calculate the gaps between consecutive meetings takes O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The provided solution sorts the input meetings in place, meaning it does not create a new array to hold the sorted meetings (assuming the sort is done in-place, which is a reasonable assumption). Beyond the input array itself, the algorithm only requires a few constant space variables to keep track of the current and next meeting being compared during the calculation of gaps, which is independent of the number of meetings, N. Therefore, the auxiliary space used is constant and does not scale with the input size. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty meeting list	Return an empty list since no meetings exist to reschedule, and therefore no free time can be generated.
Meetings overlap completely (A encompasses B)	The merging/sorting logic must correctly handle cases where one meeting interval completely contains another, combining them into one larger interval.
Adjacent meetings with no gap	The merging logic should combine adjacent meetings into a single continuous interval to avoid zero-length free time slots.
Meetings are already perfectly scheduled (no overlap, sorted)	The algorithm should still correctly identify and return the free time between the existing meeting intervals without modification.
Meetings start at the same time, different end times	Sorting needs to properly prioritize meetings with earlier start times and, when equal, consider earlier end times to ensure correct merging.
Integer overflow when calculating meeting duration/time differences	Use appropriate data types (long) or modular arithmetic if necessary, and consider the range of input values to prevent overflow errors.
Maximum number of meetings close to the memory limit	Consider using more memory-efficient data structures or algorithms to avoid exceeding memory constraints when handling a very large number of meetings.
Meetings with identical start and end times (zero-length meeting)	Treat these as valid meetings and either merge them away or ignore them during free time calculations.

Empty meeting list

How to Handle:

Return an empty list since no meetings exist to reschedule, and therefore no free time can be generated.

Meetings overlap completely (A encompasses B)

How to Handle:

The merging/sorting logic must correctly handle cases where one meeting interval completely contains another, combining them into one larger interval.

Adjacent meetings with no gap

How to Handle:

The merging logic should combine adjacent meetings into a single continuous interval to avoid zero-length free time slots.

Meetings are already perfectly scheduled (no overlap, sorted)

How to Handle:

The algorithm should still correctly identify and return the free time between the existing meeting intervals without modification.

Meetings start at the same time, different end times

How to Handle:

Sorting needs to properly prioritize meetings with earlier start times and, when equal, consider earlier end times to ensure correct merging.

Integer overflow when calculating meeting duration/time differences

How to Handle:

Use appropriate data types (long) or modular arithmetic if necessary, and consider the range of input values to prevent overflow errors.

Maximum number of meetings close to the memory limit

How to Handle:

Consider using more memory-efficient data structures or algorithms to avoid exceeding memory constraints when handling a very large number of meetings.

Meetings with identical start and end times (zero-length meeting)

How to Handle:

Treat these as valid meetings and either merge them away or ignore them during free time calculations.