重新安排会议得到最多空余时间 I

LeetCode.3439 重新安排会议得到最多空余时间 I

主要观察：移动连续的会议收益最大

因为是最多连续 k 个会议，所以我们可以把这个 k 当成一个窗口大小，移动窗口来转化成类似滑动窗口最大值的做法。窗口内的 k 个会议结合可能的左右空余时间，总共能够构成 k+1 个空闲，默认移动到一边去，留下合并后最大的相邻空闲。

也就是每次对于窗口右边界 i

• 将 i 加入窗口，此时窗口内总占用时间变为 t + (endTime[i] - startTime[i])，下标为 [i-k+1, i]
• 计算空余时间（右移）
  • 空余开始时间为 i-k 个会议的结束时间或者 0
  • 空余的结束时间为下一个会议的开始时间或者限制的 eventTime
• 移除溢出窗口的会议

class Solution {
public:
  int maxFreeTime(int eventTime, int k, vector<int> &startTime,
                  vector<int> &endTime) {
    // Sliding window
    int n = startTime.size();
    int res = 0;
    int t = 0;
 
    for (int i = 0; i < n; i++) {
      t += endTime[i] - startTime[i];
 
      int left = i <= k - 1 ? 0 : endTime[i - k];
      int right = i >= n - 1 ? eventTime : startTime[i + 1];
 
      res = max(res, right - left - t);
      if (i >= k - 1) {
        t -= endTime[i - k + 1] - startTime[i - k + 1];
      }
    }
 
    return res;
  }
};