3439. Reschedule Meetings for Maximum Free Time I

[mah-shamim]

Topics: Array, Greedy, Sliding Window

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 ith 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 <= 109
• n == startTime.length == endTime.length
• 2 <= n <= 105
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Hint:

1. In a sequence of K meetings and K + 1 gaps, you could move all meetings to the start of the sequence to get the max free time.
2. Use a sliding window of K + 1 size to store sum of gaps and take the maximum.

[mah-shamim]

We need to maximize the longest continuous period of free time during an event by rescheduling at most k meetings. The meetings are non-overlapping and must maintain their relative order after rescheduling. The key insight is that rescheduling up to k meetings allows us to merge up to k+1 consecutive gaps between meetings into a single contiguous free block. The solution involves calculating these gaps and using a sliding window technique to find the maximum sum of any k+1 consecutive gaps.

Approach

1. Calculate Gaps: The timeline is divided into gaps between meetings and the event boundaries. The first gap is from the start of the event (time 0) to the start of the first meeting. Subsequent gaps are between the end of one meeting and the start of the next. The final gap is from the end of the last meeting to the end of the event (time eventTime).
2. Determine Window Size: The maximum number of consecutive gaps we can merge is k+1 (since moving k meetings allows merging k+1 gaps). The window size is the minimum of k+1 and the total number of gaps.
3. Sliding Window Technique: Use a sliding window of size k+1 to compute the maximum sum of any consecutive k+1 gaps. This involves:
   • Calculating the sum of the first window (initial k+1 gaps).
   • Sliding the window one element at a time, adjusting the sum by subtracting the outgoing element and adding the incoming element.
   • Tracking the maximum sum encountered during this process.

Let's implement this solution in PHP: 3439. Reschedule Meetings for Maximum Free Time I

<?php
/**
 * @param Integer $eventTime
 * @param Integer $k
 * @param Integer[] $startTime
 * @param Integer[] $endTime
 * @return Integer
 */
function maxFreeTime($eventTime, $k, $startTime, $endTime) {
    $n = count($startTime);
    $gaps = array();
    $gaps[] = $startTime[0];
    for ($i = 1; $i < $n; $i++) {
        $gaps[] = $startTime[$i] - $endTime[$i-1];
    }
    $gaps[] = $eventTime - $endTime[$n-1];

    $L = min($k + 1, $n + 1);
    if ($L == 0) {
        return 0;
    }

    $current_sum = 0;
    for ($i = 0; $i < $L; $i++) {
        $current_sum += $gaps[$i];
    }
    $max_sum = $current_sum;

    $total_gaps = $n + 1;
    for ($i = $L; $i < $total_gaps; $i++) {
        $current_sum = $current_sum - $gaps[$i - $L] + $gaps[$i];
        if ($current_sum > $max_sum) {
            $max_sum = $current_sum;
        }
    }

    return $max_sum;
}

// Test cases
echo maxFreeTime(5, 1, array(1, 3), array(2, 5)) . "\n"; // Output: 2
echo maxFreeTime(10, 1, array(0, 2, 9), array(1, 4, 10)) . "\n"; // Output: 6
echo maxFreeTime(5, 2, array(0, 1, 2, 3, 4), array(1, 2, 3, 4, 5)) . "\n"; // Output: 0
?>

Explanation:

1. Gap Calculation: The gaps array is constructed where:
   • The first element is the gap from the start of the event to the first meeting (startTime[0]).
   • Subsequent elements are the gaps between the end of the previous meeting and the start of the next (startTime[i] - endTime[i-1]).
   • The last element is the gap from the end of the last meeting to the end of the event (eventTime - endTime[n-1]).
2. Window Size: The window size L is set to the minimum of k+1 (the maximum gaps we can merge) and the total number of gaps (n+1).
3. Sliding Window:
   • The initial window sum is calculated for the first L gaps.
   • The window is then slid across the gaps array, adjusting the sum by removing the leftmost element of the previous window and adding the new rightmost element.
   • The maximum sum encountered during this process is stored and returned as the result, representing the largest contiguous free time achievable by rescheduling up to k meetings.

This approach efficiently computes the solution by leveraging the properties of non-negative gaps and the sliding window technique to find the optimal segment of gaps to merge, ensuring optimal performance even for large inputs.

[basharul-siddike]

Thanks for solving the problem of "Reschedule Meetings for Maximum Free Time I"

[mah-shamim]

Thanks