Reschedule Meetings for Maximum Free Time
Fivetran● MediumFULLTIMEOAProblem statement
An event runs from time 0 to time eventTime. During the event there are n meetings that do not overlap. Meeting i starts at startTime[i] and ends at endTime[i], and the meetings are given in time order.
You may reschedule at most k meetings. To reschedule a meeting, move it to a new start time while keeping its length the same. After all moves:
- the meetings must keep the same order as before,
- no two meetings may overlap, though one may start exactly when another ends, and
- every meeting must stay inside the event, from
0toeventTime.
Free time is any time during the event that is not inside a meeting. Return the length of the longest stretch of continuous free time you can create.
Function
maxFreeTime(eventTime: int, k: int, startTime: int[], endTime: int[]) → intExamples
Example 1
eventTime = 10k = 1startTime = [2,5]endTime = [3,7]return = 5Move the second meeting from [5, 7] to [3, 5], right after the first one ends. The time from 5 to 10 is then free, which is 5 units long.
Moving only the first meeting cannot do better: the longest free stretch would then be the 4 units before the second meeting starts, or the 3 units after it ends.
Example 2
eventTime = 12k = 2startTime = [0,4,9]endTime = [2,6,10]return = 7Keep the first meeting at [0, 2]. Move the second meeting to [2, 4] and the third to [4, 5]. The time from 5 to 12 is free, so the answer is 7.
Example 3
eventTime = 6k = 1startTime = [0,2,4]endTime = [2,4,6]return = 0The meetings fill the whole event with no gaps. Moving a meeting cannot open any free time, because the total length of the meetings equals eventTime. The answer is 0.
Constraints
1 <= eventTime <= 10^9n == startTime.length == endTime.length2 <= n <= 2 * 10^41 <= k <= n0 <= startTime[i] < endTime[i] <= eventTimeendTime[i] <= startTime[i + 1]for everyifrom0ton - 2