09_Reschedule_Meetings_for_Maximum_Free_Time_I.cpp

// 3439. Reschedule Meetings for Maximum Free Time I

// 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].

class Solution
{
public:
    int maxFreeTime(int eventTime, int k, vector<int> &startTime, vector<int> &endTime)
    {
        int count = startTime.size();
        vector<int> prefixSum(count + 1, 0);
        int maxFree = 0;

        for (int i = 0; i < count; ++i)
        {
            prefixSum[i + 1] = prefixSum[i] + (endTime[i] - startTime[i]);
        }

        for (int i = k - 1; i < count; ++i)
        {
            int occupied = prefixSum[i + 1] - prefixSum[i - k + 1];
            int windowEnd = (i == count - 1) ? eventTime : startTime[i + 1];
            int windowStart = (i == k - 1) ? 0 : endTime[i - k];
            int freeTime = windowEnd - windowStart - occupied;
            maxFree = max(maxFree, freeTime);
        }

        return maxFree;
    }
};

/*
This code finds the maximum free time possible after rearranging k meetings within an event period.

The algorithm works as follows:
1. Creates a prefix sum array to store cumulative meeting durations
2. For each window of k meetings:
   - Calculates total occupied time using prefix sum
   - Determines window boundaries (start and end times)
   - Computes free time by subtracting occupied time from window duration
   - Updates maximum free time if current is larger

Time Complexity: O(n) where n is the number of meetings
Space Complexity: O(n) for the prefix sum array
*/