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

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]

输出：2

解释：

将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]

输出：6

解释：

将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]

输出：0

解释：

活动中的所有时间都被会议安排满了。

提示：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

分析：先用一个数组记录所有活动完成时间的前缀和。之后从第 1 个活动开始，每次选定 k 个活动，把这个 k 个活动全部移动到前一个活动的结束时间开始处排列，再用下一个活动的开始时间减去前一个活动结束时间加上 k 个活动的持续时间之和，得到一个结果。保留最大的结果即可。

注意第 1 个活动的开始时间可能不为 0，因此在处理第一次的情况时，要把第一个活动设定为 0 开始；同样最后一个活动的结束时间不一定为 eventTime，在处理最后 k 个活动时，需要把最后一个活动的结束时间设定为 eventTime，此时前面还能移动 k-1 个活动。

int maxFreeTime(int eventTime, int k, int* startTime, int startTimeSize, int* endTime, int endTimeSize) {
    int n=startTimeSize,ans=0,ret=0;
    int lastTime[n+6],left_preTime[n+6];
    for(int i=0;i<n;++i)
    {
        left_preTime[i]=lastTime[i]=endTime[i]-startTime[i];
        if(i)left_preTime[i]+=left_preTime[i-1];
    }

    if(k==n)return eventTime-lastTime[k-1]-left_preTime[k-2];

    for(int i=0;i<=n-k;++i)
    {
        int right,len=left_preTime[k-1+i],last=0;
        if(!i) last=len,right=startTime[k+i];
        else if(i<n-k)last=len+endTime[i-1]-left_preTime[i-1],right=startTime[k+i];
        else 
        {
            right=eventTime-lastTime[n-1],last=left_preTime[k-2+i]+endTime[i-1]-left_preTime[i-1];
        }
        ans=fmax(right-last,ans);

        // printf("i=%d,len=%d,right=%d,ans=%d\n",i,len,right,ans);
    }
    return ans;
}