leetcode 2054. 两个最好的不重叠活动 中等

给你一个下标从0开始的二维整数数组events，其中events[i] = [startTimei, endTimei, valuei]。第i个活动开始于startTimei，结束于endTimei，如果你参加这个活动，那么你可以得到价值valuei。你最多可以参加两个时间不重叠活动，使得它们的价值之和最大。

请你返回价值之和的最大值。

注意，活动的开始时间和结束时间是包括在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为t，那么下一个活动必须在t + 1或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]输出：4解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

输入：events = [[1,3,2],[4,5,2],[1,5,5]]输出：5解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]输出：8解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

提示：

• 2 <= events.length <= 10^5
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 10^9
• 1 <= valuei <= 10^6

分析：设取的第二个活动开始时间为 startTime，则问题转化为：遍历所有活动（作为取的第二个活动），如何取第一个活动使得参加的两个活动价值最大。

按照结束时间从小到大排序后，假设有如下两个活动：活动 A 结束于 3 时刻，价值 999。活动 B 结束于 6 时刻，价值 9。因为我们已经取了要参加的第二个活动，所以对于上面的这两个活动不关心开始时间。很明显，活动 B 是没有意义的，因为它的结束时间更晚，而价值更低。对于同样的第二个活动开始时间，取活动 A 作为第一个活动是更优的，活动 B 可以完全被活动 A 代替。

可以用一个数组，按照结束时间从小到大，活动价值从小到大记录可选的活动。由于之前已经按照结束时间升序排序，记录时只需要按照活动价值从小到大记录即可，类似于活动 A 和活动 B 的情况，只记录活动 A 即可。

遍历所有活动时，可以对这个记录数组进行二分查找，找到一个价值最大，且结束时间小于开始时间的活动，如果找不到，则当前活动只能单独取。最后取最大值作为答案。

typedef struct node { int endTime,value; }node; int cmp(const void *a,const void *b) { node *aa=(node*)a; node *bb=(node*)b; if(aa->endTime!=bb->endTime)return aa->endTime-bb->endTime; return aa->value-bb->value; } int maxTwoEvents(int** events, int eventsSize, int* eventsColSize) { node num[eventsSize+5],val[eventsSize+5]; for(int i=0;i<eventsSize;++i) num[i].endTime=events[i][1],num[i].value=events[i][2]; qsort(num,eventsSize,sizeof(node),cmp); int cnt=1; val[0].endTime=0,val[0].value=0; for(int i=0;i<eventsSize;++i) if(num[i].value>val[cnt-1].value)val[cnt]=num[i],cnt++; int ans=0; for(int i=0;i<eventsSize;++i) { int l=0,r=cnt,st=events[i][0],temp=events[i][2]; while(l<r) { int mid=(l+r)/2; if(val[mid].endTime<st)temp=val[mid].value+events[i][2],l=mid+1; else r=mid; } ans=fmax(ans,temp); } return ans; }