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<sup>th</sup>
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.
Example:
eventTime
= 10, startTime
= [0, 3, 7, 9], endTime
= [1, 4, 8, 10]
What is the maximum free time after rescheduling?
The simplest approach is to iterate through each meeting, reschedule it to every possible valid time slot, and calculate the maximum free time for each rescheduling. We keep track of the overall maximum free time found so far.
i
, store its original start and end times.eventTime
.i
back to it's original start and end times.This approach is extremely inefficient due to its nested loops and overlap checks.
The optimal approach involves these steps:
eventTime
.eventTime
.def solve():
eventTime = 10
startTime = [0, 3, 7, 9]
endTime = [1, 4, 8, 10]
n = len(startTime)
meetings = sorted(zip(startTime, endTime))
def calculate_max_free_time(meetings_list):
meetings_list.sort()
max_free = max(meetings_list[0][0], eventTime - meetings_list[-1][1])
for i in range(len(meetings_list) - 1):
max_free = max(max_free, meetings_list[i+1][0] - meetings_list[i][1])
return max_free
max_free_time = calculate_max_free_time(meetings)
for i in range(n):
original_start, original_end = meetings[i]
# Try moving the meeting to the beginning
new_meetings = meetings[:i] + meetings[i+1:]
new_start = 0
new_end = original_end - original_start
valid = True
for start, end in new_meetings:
if not (new_end <= start or new_start >= end):
valid = False
break
if valid:
max_free_time = max(max_free_time, calculate_max_free_time(new_meetings + [(new_start, new_end)]))
# Try moving the meeting to the end
new_meetings = meetings[:i] + meetings[i+1:]
new_start = eventTime - (original_end - original_start)
new_end = eventTime
valid = True
for start, end in new_meetings:
if not (new_end <= start or new_start >= end):
valid = False
break
if valid:
max_free_time = max(max_free_time, calculate_max_free_time(new_meetings + [(new_start, new_end)]))
# Try moving the meeting to other spots
for j in range(len(meetings)):
if j != i:
new_meetings = meetings[:i] + meetings[i+1:]
new_start = meetings[j][1]
new_end = new_start + (original_end - original_start)
if new_end > eventTime:
continue
valid = True
for start, end in new_meetings:
if not (new_end <= start or new_start >= end):
valid = False
break
if valid:
max_free_time = max(max_free_time, calculate_max_free_time(new_meetings + [(new_start, new_end)]))
print(max_free_time)
solve()