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

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

思路

这道题的核心思路是：一定是安排连续的k个会议才能求出最大空闲时间。

为什么？如图，k=2，安排两个会议。

不难发现，重新安排连续的2和3能得到最大值5。如果安排不连续的2和4，那么安排4得到的空间时间对2并没有帮助，因为中间有3相隔，得到的空闲时间无法拼凑一起得到连续的空闲时间。

因此，必定是安排连续k个会议，才能得到最大空闲时间。就转化成了定长滑动窗口问题。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

Code

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;

        int freeTime = 0;
        int s = 0;
        for(int i = 0;i < n;i ++){
            s += endTime[i] - startTime[i];
            if(i - k + 1 < 0){
                continue;
            }
            
            int end = eventTime;
            int begin = 0;
            int l = i - k + 1;
            if(l > 0){
                begin = endTime[l - 1];
            }
            if(i != n-1){
                end = startTime[i + 1];
            }
            freeTime = Math.max(freeTime, end-begin-s);

            s -= endTime[i-k+1] - startTime[i-k+1];
            
        }
        return freeTime;
    }
}