leetcode 2054（排序 + 单调栈，通用做法是 DP）

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; } };