3440. Reschedule Meetings for Maximum Free Time II

[mah-shamim]

Topics: Array, Greedy, Enumeration

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 ith 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.

Note: In this version, it is valid for the relative ordering of the meetings to change after rescheduling one meeting.

Example 1:

• Input: eventTime = 5, 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, startTime = [0,7,9], endTime = [1,8,10]
• Output: 7
• Explanation:
  
  • Reschedule the meeting at [0, 1] to [8, 9], leaving no meetings during the time [0, 7].

Example 3:

• Input: eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]
• Output: 6
• Explanation:
  
  • Reschedule the meeting at [3, 4] to [8, 9], leaving no meetings during the time [1, 7].

Example 4:

• Input: eventTime = 5, 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
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2]

Hint:

1. If we reschedule a meeting earlier or later, we need to find a gap of length at least endTime[i] - startTime[i]. Try maintaining the gaps in some sorted data structure.

[mah-shamim]

We need to maximize the longest continuous period of free time during an event by rescheduling at most one meeting. The meetings are initially non-overlapping, and we can move one meeting to any available gap that can accommodate its duration without overlapping with other meetings. The goal is to find the maximum free time achievable after such a rescheduling.

Approach

1. Initial Setup: Calculate the initial gaps between meetings, including the gaps before the first meeting, between consecutive meetings, and after the last meeting.
2. Original Maximum Gap: Compute the maximum gap from the initial gaps. This serves as the baseline if no meetings are moved.
3. Evaluate Each Meeting: For each meeting, simulate its removal and calculate the new gaps that would result. This involves merging the adjacent gaps where the meeting was removed.
4. Check for Valid Moves: For each removed meeting, check if there exists a gap (in the new set of gaps) that can accommodate the meeting's duration. If not, skip this meeting.
5. Calculate Candidate Maximum Gap:
   • If there exists a gap (other than the largest one) that can accommodate the meeting, the maximum gap remains the same as the largest gap in the new set.
   • If the largest gap is the only one that can accommodate the meeting, breaking it might reduce the maximum gap. In this case, the new maximum gap is the maximum between the second largest gap and the largest gap minus the meeting's duration.
6. Update Result: Track the maximum gap obtained from moving each meeting and compare it with the original maximum gap to determine the final result.

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

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

    $total_gaps = $n + 1;
    $prefix_max = array_fill(0, $total_gaps + 1, -1);
    $prefix_second_max = array_fill(0, $total_gaps + 1, -1);
    $prefix_max_count = array_fill(0, $total_gaps + 1, 0);

    for ($i = 0; $i < $total_gaps; $i++) {
        $cur = $original_gaps[$i];
        $cur_max = $prefix_max[$i];
        $cur_second = $prefix_second_max[$i];
        if ($cur > $cur_max) {
            $prefix_max[$i + 1] = $cur;
            $prefix_second_max[$i + 1] = max($cur_second, $cur_max);
            $prefix_max_count[$i + 1] = 1;
        } else if ($cur == $cur_max) {
            $prefix_max[$i + 1] = $cur_max;
            $prefix_second_max[$i + 1] = $cur_second;
            $prefix_max_count[$i + 1] = $prefix_max_count[$i] + 1;
        } else {
            $prefix_max[$i + 1] = $cur_max;
            if ($cur > $cur_second) {
                $prefix_second_max[$i + 1] = $cur;
            } else {
                $prefix_second_max[$i + 1] = $cur_second;
            }
            $prefix_max_count[$i + 1] = $prefix_max_count[$i];
        }
    }

    $suffix_max = array_fill(0, $total_gaps + 2, -1);
    $suffix_second_max = array_fill(0, $total_gaps + 2, -1);
    $suffix_max_count = array_fill(0, $total_gaps + 2, 0);
    $suffix_max[$total_gaps + 1] = -1;
    $suffix_second_max[$total_gaps + 1] = -1;
    $suffix_max_count[$total_gaps + 1] = 0;

    for ($i = $total_gaps - 1; $i >= 0; $i--) {
        $cur = $original_gaps[$i];
        $cur_max = $suffix_max[$i + 1];
        $cur_second = $suffix_second_max[$i + 1];
        if ($cur > $cur_max) {
            $suffix_max[$i] = $cur;
            $suffix_second_max[$i] = max($cur_second, $cur_max);
            $suffix_max_count[$i] = 1;
        } else if ($cur == $cur_max) {
            $suffix_max[$i] = $cur_max;
            $suffix_second_max[$i] = $cur_second;
            $suffix_max_count[$i] = $suffix_max_count[$i + 1] + 1;
        } else {
            $suffix_max[$i] = $cur_max;
            if ($cur > $cur_second) {
                $suffix_second_max[$i] = $cur;
            } else {
                $suffix_second_max[$i] = $cur_second;
            }
            $suffix_max_count[$i] = $suffix_max_count[$i + 1];
        }
    }

    $ans = max($original_gaps);

    for ($i = 0; $i < $n; $i++) {
        $duration = $endTime[$i] - $startTime[$i];
        if ($i == 0) {
            $merged = $startTime[1];
        } else if ($i == $n - 1) {
            $merged = $eventTime - $endTime[$n - 2];
        } else {
            $merged = $startTime[$i + 1] - $endTime[$i - 1];
        }

        $maxA = ($i > 0) ? $prefix_max[$i] : -1;
        $second_maxA = ($i > 0) ? $prefix_second_max[$i] : -1;
        $count_maxA = ($i > 0) ? $prefix_max_count[$i] : 0;

        $index_suffix = $i + 2;
        if ($index_suffix <= $total_gaps) {
            $maxC = $suffix_max[$index_suffix];
            $second_maxC = $suffix_second_max[$index_suffix];
            $count_maxC = $suffix_max_count[$index_suffix];
        } else {
            $maxC = -1;
            $second_maxC = -1;
            $count_maxC = 0;
        }

        $max_all = max($maxA, $merged, $maxC);
        if ($max_all < $duration) {
            continue;
        }

        $condition = false;
        if ($maxA >= $duration && $maxA < $max_all) {
            $condition = true;
        }
        if ($merged >= $duration && $merged < $max_all) {
            $condition = true;
        }
        if ($maxC >= $duration && $maxC < $max_all) {
            $condition = true;
        }

        if ($condition) {
            $ans = max($ans, $max_all);
        } else {
            $count = 0;
            if ($maxA == $max_all) {
                $count += $count_maxA;
            }
            if ($merged == $max_all) {
                $count += 1;
            }
            if ($maxC == $max_all) {
                $count += $count_maxC;
            }
            if ($count >= 2) {
                $ans = max($ans, $max_all);
            } else {
                $candidate_from_A = ($maxA < $max_all) ? $maxA : $second_maxA;
                $candidate_from_merged = ($merged < $max_all) ? $merged : -1;
                $candidate_from_C = ($maxC < $max_all) ? $maxC : $second_maxC;
                $second_max_val = max($candidate_from_A, $candidate_from_merged, $candidate_from_C);
                $candidate_i = max($second_max_val, $max_all - $duration);
                $ans = max($ans, $candidate_i);
            }
        }
    }

    return $ans;
}

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

Explanation:

1. Initial Setup: The initial gaps between meetings are calculated, including the gaps before the first meeting, between consecutive meetings, and after the last meeting.
2. Prefix and Suffix Arrays: These arrays store the maximum and second maximum values along with their counts for all possible subarrays. This helps in efficiently determining the largest and second largest gaps when any meeting is removed.
3. Processing Each Meeting: For each meeting, we:
   • Calculate the new gap formed by merging adjacent gaps when the meeting is removed.
   • Determine if there exists a gap that can accommodate the meeting's duration.
   • Compute the new maximum free time by considering the largest remaining gap or the largest gap reduced by the meeting's duration if necessary.
4. Result Calculation: The result is the maximum value between the original maximum gap and the best gap obtained by moving any single meeting.

This approach efficiently checks all possible moves of a single meeting to maximize the free time, leveraging precomputed prefix and suffix arrays for optimal performance.

[kovatz]

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

[mah-shamim]

Thanks