Reschedule Meetings for Maximum Free Time I
Source: leetcode
Difficulty: Medium
Tags: 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:**


![](https://assets.leetcode.com/uploads/2024/12/21/example0_rescheduled.png)


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:**


![](https://assets.leetcode.com/uploads/2024/12/21/example1_rescheduled.png)


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




C++ solution:
class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        vector<int> gaps;
        int n = startTime.size();
        gaps.push_back(startTime[0]);
        for (int i = 1; i < n; ++i) {
            gaps.push_back(startTime[i] - endTime[i-1]);
        }
        gaps.push_back(eventTime - endTime.back());
        int m = gaps.size();
        if (m <= k + 1) {
            long long total = 0;
            for (int g : gaps) {
                total += g;
            }
            return total;
        }
        long long current_sum = 0;
        for (int i = 0; i < k + 1; ++i) {
            current_sum += gaps[i];
        }
        long long max_sum = current_sum;
        for (int i = k + 1; i < m; ++i) {
            current_sum += gaps[i] - gaps[i - (k + 1)];
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
        return max_sum;
    }
};

Go solution:
func maxFreeTime(eventTime int, k int, startTime []int, endTime []int) int {
    n := len(startTime)
    if n == 0 {
        return eventTime
    }
    gaps := []int{startTime[0]}
    for i := 1; i < n; i++ {
        gaps = append(gaps, startTime[i]-endTime[i-1])
    }
    gaps = append(gaps, eventTime-endTime[n-1])
    
    s := k + 1
    if s > len(gaps) {
        s = len(gaps)
    }
    if s == 0 {
        return 0
    }
    
    currentSum := 0
    for i := 0; i < s; i++ {
        currentSum += gaps[i]
    }
    maxSum := currentSum
    for i := s; i < len(gaps); i++ {
        currentSum += gaps[i] - gaps[i-s]
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    return maxSum
}

Java solution:
class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        List<Long> gaps = new ArrayList<>();
        int n = startTime.length;
        gaps.add((long) startTime[0] - 0L);
        for (int i = 1; i < n; i++) {
            gaps.add((long) startTime[i] - endTime[i - 1]);
        }
        gaps.add((long) eventTime - endTime[n - 1]);
        
        int m = gaps.size();
        int windowSize = k + 1;
        if (windowSize >= m) {
            long total = 0;
            for (long gap : gaps) {
                total += gap;
            }
            return (int) total;
        }
        
        long maxSum = 0;
        long currentSum = 0;
        for (int i = 0; i < windowSize; i++) {
            currentSum += gaps.get(i);
        }
        maxSum = currentSum;
        for (int i = windowSize; i < m; i++) {
            currentSum += gaps.get(i) - gaps.get(i - windowSize);
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return (int) maxSum;
    }
}

JavaScript solution:
var maxFreeTime = function(eventTime, k, startTime, endTime) {
    const n = startTime.length;
    const free = [];
    let prevEnd = 0;
    for (let i = 0; i < n; i++) {
        const currentStart = startTime[i];
        free.push(currentStart - prevEnd);
        prevEnd = endTime[i];
    }
    free.push(eventTime - prevEnd);
    
    let maxFree = 0;
    for (const val of free) {
        if (val > maxFree) {
            maxFree = val;
        }
    }
    
    const totalSum = free.reduce((a, b) => a + b, 0);
    const m = free.length;
    let sumMax;
    
    if (k + 1 >= m) {
        sumMax = totalSum;
    } else {
        let currentSum = 0;
        for (let i = 0; i < k + 1; i++) {
            currentSum += free[i];
        }
        sumMax = currentSum;
        for (let i = k + 1; i < m; i++) {
            currentSum += free[i] - free[i - (k + 1)];
            sumMax = Math.max(sumMax, currentSum);
        }
    }
    
    return Math.max(maxFree, sumMax);
};

Python solution:
class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        gaps = []
        gaps.append(startTime[0])
        for i in range(n - 1):
            gaps.append(startTime[i + 1] - endTime[i])
        gaps.append(eventTime - endTime[-1])
        
        window_size = k + 1
        if len(gaps) <= window_size:
            return sum(gaps)
        
        current_sum = sum(gaps[:window_size])
        max_sum = current_sum
        for i in range(window_size, len(gaps)):
            current_sum += gaps[i] - gaps[i - window_size]
            if current_sum > max_sum:
                max_sum = current_sum
        
        return max_sum

Ruby solution:
def max_free_time(event_time, k, start_time, end_time)
    gaps = []
    gaps << start_time[0] - 0

    (0...start_time.size-1).each do |i|
        gaps << start_time[i+1] - end_time[i]
    end

    gaps << event_time - end_time[-1]

    max_gap = gaps.max
    window_size = k + 1
    m = gaps.size

    if window_size > m
        sum_all = gaps.sum
        return [max_gap, sum_all].max
    end

    current_sum = gaps[0, window_size].sum
    max_sum = current_sum

    (window_size...m).each do |i|
        current_sum += gaps[i] - gaps[i - window_size]
        max_sum = [max_sum, current_sum].max
    end

    [max_gap, max_sum].max
end