2054: 两个最好的不重叠活动
题意：在结束时间小于 startTime 的活动中，选择价值最大的活动。
为了方便查找，先把 events 按照结束时间从小到大排序。
排序后，对比如下两个活动：
- 活动一：结束于 3 时刻，价值 999。
- 活动二：结束于 6 时刻，价值 9。
活动二的结束时间又晚，价值又小，全方面不如活动一，是垃圾数据，直接忽略。
换句话说，在遍历 events 的过程中（注意 events 已按照结束时间排序），只在遇到更大价值的活动时，才记录该活动。把这些活动记录到一个栈（列表）中，那么从栈底到栈顶，结束时间是递增的，价值也是递增的，非常适合二分查找。
枚举第二个活动，在单调栈中二分查找结束时间严格小于 startTime 的最后一个活动，即为价值最大的第一个活动。如果没找到，那么只能选一个活动。
为了简化判断逻辑，可以在栈底加一个结束时间为 0，价值也为 0 的哨兵。
ranges::sort(events,{},[](auto& e){return e[1];});vector<pair<int,int>> st={{0,0}}; //栈底哨兵auto it=--ranges::lower_bound(st,start_time,{},&pair<int,int>::first); ans=max(ans,it->second+value);单调栈递增，如果找不到，因为有“栈底哨兵”，因此找不到满足条件的活动时，it={0,0}，it->second=0，不会越界。
class Solution { public: int maxTwoEvents(vector<vector<int>>& events) { //按照结束时间升序排序 ranges::sort(events,{},[](auto& e){return e[1];}); //从栈底到栈顶，结束时间递增，价值递增 vector<pair<int,int>> st={{0,0}}; //栈底哨兵 int ans=0; for(auto& e:events){ int start_time=e[0],value=e[2]; //二分查找最后一个结束时间 < start_time 的活动 auto it=--ranges::lower_bound(st,start_time,{},&pair<int,int>::first); ans=max(ans,it->second+value); if(value>st.back().second) st.emplace_back(e[1],value); } return ans; } };
