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

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

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

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

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

注意，会议 不能 安排到整个活动的时间以外，且会议之间需要保持互不重叠。

注意：重新安排会议以后，会议之间的顺序可以发生改变。

示例 1：

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

输出：2

解释：

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

示例 2：

输入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]

输出：7

解释：

将 [0, 1] 的会议安排到 [8, 9] ，得到空余时间 [0, 7] 。

示例 3：

输入：eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]

输出：6

解释：

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

示例 4：

输入：eventTime = 5, 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
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

分析：首先预处理出每两个会议之间的间隔。对于每一个会议，如果存在一个不是它左右会议的间隔时间大于它的持续时间，说明可以把这个会议移动到其它会议之间，从而使得它的前后会议之间间隔变大；如果不存在这样的间隔时间，则把这个会议的开始时间设定为前一个会议的结束时间，计算间隔。

注意第一个会议和最后一个会议。第一个会议可以移动到最后一个会议的右边，最后一个会议可以移动到第一个会议的左边。

3439 是移动 k 个会议，但要保持相对顺序；3440 则只能移动一个，但可以不考虑相对顺序。两道题都是贪心。

int cmp(const void *a,const void *b)
{return *(int*)a-*(int*)b;
}int maxFreeTime(int eventTime, int* startTime, int startTimeSize, int* endTime, int endTimeSize) {int ans=0,n=startTimeSize,t=0;int temp[n+5],interval[n+5],cnt[n+5];for(int i=1;i<n;++i)temp[i-1]=startTime[i]-endTime[i-1];qsort(temp,n-1,sizeof(int),cmp);interval[t]=temp[0];cnt[0]=1;int sum=1,flag=0;for(int i=1;i<=n-1;++i){if(temp[i]!=interval[t]||i==n-1)cnt[t++]=sum,interval[t]=temp[i],sum=1;else sum++;}// printf("t=%d\n",t);// for(int i=0;i<t;++i)// {//     printf("interval=%d cnt=%d\n",interval[i],cnt[i]);// }for(int i=0;i<n;++i){if(!i){int last=endTime[0]-startTime[0],right=startTime[1]-endTime[0];ans=fmax(ans,startTime[1]-last);ans=fmax(ans,startTime[0]-0);bool flag=0;if(eventTime-endTime[n-1]>=last)flag=1;if(!flag){for(int j=t-1;j>=0;--j){if(interval[j]>=last){if(interval[j]!=right)flag=1;else if(interval[j]==right&&cnt[j]>1)flag=1;}if(flag)break;if(interval[j]<last)break;}}if(flag)ans=fmax(startTime[1],ans);// printf("i=%d flag=%d ans=%d\n",i,flag,ans);}else if(i==n-1){int last=endTime[n-1]-startTime[n-1],left=startTime[i]-endTime[i-1];ans=fmax(ans,eventTime-last-endTime[n-2]);ans=fmax(ans,eventTime-endTime[n-1]);bool flag=0;if(startTime[0]-0>=last)flag=1;if(!flag){for(int j=t-1;j>=0;--j){if(interval[j]>=last){if(interval[j]!=left)flag=1;else if(interval[j]==left&&cnt[j]>1)flag=1;}if(flag)break;if(interval[j]<last)break;}}if(flag)ans=fmax(eventTime-endTime[n-2],ans);// printf("i=%d flag=%d ans=%d\n",i,flag,ans);}else{int last=endTime[i]-startTime[i],left=startTime[i]-endTime[i-1],right=startTime[i+1]-endTime[i];int x=1;if(left==right)x=2;bool flag=0;for(int j=t-1;j>=0;--j){if(interval[j]>=last){if(interval[j]!=left&&right!=interval[j])flag=1;else if(interval[j]==left&&cnt[j]>x)flag=1;else if(interval[j]==right&&cnt[j]>x)flag=1;}if(flag)break;if(interval[j]<last)break;}if(!flag){if(eventTime-endTime[n-1]>=last||startTime[0]>=last)flag=1;}if(flag)ans=fmax(ans,startTime[i+1]-endTime[i-1]);else ans=fmax(ans,startTime[i+1]-endTime[i-1]-last);// printf("i=%d start=%d end=%d flag=%d ans=%d\n",i,startTime[i],endTime[i],flag,ans);}}return ans;
}