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.

Two Pointer Solution

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& S, vector<int>& E) {
        int res = 0, sum = 0;
        for(int i = 0; i < S.size(); i++) {
            sum += E[i] - S[i];
            if(i >= k) sum -= E[i-k] - S[i-k];
            int st = i >= k ? E[i-k] : 0;
            int ed = i + 1 == S.size() ? eventTime : S[i+1];
            res = max(res, ed - st - sum);
        }
        return res;
    }
};

Binary Search Solution

class Solution {
    bool helper(vector<int>& S, vector<int>& E, int k, int t, int x) {
        for(int i = 0, sum = 0; i < S.size(); i++) {
            sum += E[i] - S[i];
            if(i >= k) sum -= E[i-k] - S[i-k];
            int st = i >= k ? E[i-k] : 0;
            int ed = i + 1 == S.size() ? x : S[i+1];
            if(ed - st - sum >= t) return true;
        }
        return false;
    }
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int l = 0, r = eventTime, res = eventTime;
        while(l <= r) {
            int m = l + (r - l) / 2;
            bool ok = helper(startTime, endTime, k, m, eventTime);
            if(ok) {
                l = m + 1;
                res = m;
            } else r = m - 1;
        }
        return res;
    }
};