Practice/Google/Leetcode 3439. Reschedule Meetings for Maximum Free Time I

Leetcode 3439. Reschedule Meetings for Maximum Free Time I

CodingOptional

Problem

You are managing a schedule for an event that spans from time 0 to time eventTime. During this period, there are n non-overlapping meetings already scheduled, where each meeting i occupies the time interval [start_i, end_i].

You have the ability to reschedule up to k meetings. When you reschedule a meeting, you must:

• Keep the meeting's duration unchanged
• Maintain the relative order of all meetings (a meeting that originally came before another must still come before it after rescheduling)
• Ensure the rescheduled meeting stays within the bounds [0, eventTime]
• Ensure meetings remain non-overlapping

Your goal is to maximize the length of the longest continuous block of free time in the schedule after optimally rescheduling up to k meetings.

Return the maximum possible length of a continuous free time block.

Requirements

1. Meetings can be shifted to any valid position while maintaining their duration
2. The relative order of meetings must be preserved (no reordering)
3. All meetings must remain within [0, eventTime] after rescheduling
4. Meetings must not overlap after rescheduling
5. You can reschedule at most k meetings

Constraints

• 0 <= n <= 100,000 (number of meetings)
• 1 <= eventTime <= 1,000,000,000
• 0 <= k <= n
• 0 <= start_i < end_i <= eventTime for all meetings
• Meetings are initially non-overlapping
• Time complexity should be O(n) or O(n log n)
• Space complexity should be O(n)

Examples

Example 1:

Input: meetings = [[1, 3], [5, 7]], eventTime = 10, k = 1 Output: 6 Explanation: By moving the second meeting [5, 7] to [4, 6], we create a gap from [6, 10] of length 4. Alternatively, moving it to the end [8, 10] creates a gap [1, 8] of length 6 (after removing the first meeting's impact). The optimal strategy creates a 6-unit gap.

Example 2:

Input: meetings = [[2, 4], [6, 8]], eventTime = 10, k = 0 Output: 2 Explanation: Without moving any meetings, we have gaps [0, 2], [4, 6], and [8, 10], each of length 2.

Example 3:

Input: meetings = [[0, 5]], eventTime = 10, k = 1 Output: 10 Explanation: Since we can move the only meeting, we can shift it to create a 10-unit gap by compressing it to one end.