贪心（七）2054. 两个最好的不重叠活动

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 。

实现一个结构体event，分别存放每个时间戳，不管是开始时间还是结束时间，以及这段时间的val，并使用_op字段表示 这个时间戳是开始为0，还是结束为1.

将所有的时间戳放入vector<event> evs数组中，使用sort按照时间戳和_op进行升序排序

使用如下的sort函数进行比较

也可以使用lambda表达式进行比较

用best_first来记录当前遇到的最大的值，当遇到一个结束时间戳时，就使用当前的val来不断维护一个最大的best_first值

当遇到一个开始时间时，用当前遇到的val+之前的最大值best_first来维护一个最大的结果res值

sort(evs.begin(), evs.end(), [](const event& left, const event& right) { if (left._time != right._time) return left._time < right._time; if (left._op != right._op) return left._op < right._op; return left._val < right._val; });

struct event { int _time; int _op; int _val; event(int time, int op, int val) : _time(time) , _op(op) , _val(val) {} bool operator<(event& evt) // 类内进行比较需要重载<的比较方式 { // sort(evs.begin(),evs.end()) // 函数内部自己会调用<重载来构建 if(_time != evt._time) return _time < evt._time; else return _op < evt._op; } }; class Com1 // 类外传递Com()的比较方式 { public: bool operator()(event&left, event&right) { if(left._time != right._time) return left._time < right._time; else return left._op < right._op; } }; class Com2 // 使用 std::tie 实现简洁正确的比较 { // std::tie 会自动创建元组进行比较，完全符合严格弱序要求。 public: bool operator()(event&left, event&right) { return std::tie(left._time, left._op) < std::tie(right._time, right._op); } }; class Solution { public: int maxTwoEvents(vector<vector<int>>& events) { vector<event> evs; for(auto & e : events) { evs.emplace_back(e[0], 0, e[2]); evs.emplace_back(e[1], 1, e[2]); } sort(evs.begin(), evs.end(), Com2()); int res = 0, best_first = 0; for(auto &e : evs) { if(e._op == 0) { res = max(res, e._val + best_first); } else { best_first = max(best_first, e._val); } } return res; } };