leetcode2054

leetcode 2054

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>using namespace std;struct Event {// 时间戳int ts;// op = 0 表示左边界，op = 1 表示右边界int op;int val;Event(int _ts, int _op, int _val): ts(_ts), op(_op), val(_val) {}bool operator< (const Event& that) const {return tie(ts, op) < tie(that.ts, that.op);}
};class Solution {
public:int maxTwoEvents(vector<vector<int> >& events) {vector<Event> evs;for (const auto& event : events) {evs.emplace_back(event[0], 0, event[2]);evs.emplace_back(event[1], 1, event[2]);}sort(evs.begin(), evs.end());for (const auto& row : evs) {std::cout << row.ts << ","<< row.op << ","<< row.val << " ";std::cout << std::endl;}int ans = 0, bestFirst = 0;for(int i=0; i<evs.size(); i++){int cur_ts = evs[i].ts;int cur_op = evs[i].op;int cur_val = evs[i].val;if (cur_op == 0) {ans = max(ans, cur_val + bestFirst);}else {bestFirst = max(bestFirst, cur_val);};}return ans;}
};int main(){vector<vector<int> > events = {{1,3,2},{4,5,2},{2,4,3}};// for (const auto& row : events) {//     for (const auto& element : row) {//         std::cout << element << " ";//     }//     std::cout << std::endl;// }Solution s;int ans = s.maxTwoEvents(events);return 0;
}

(ith start_time, ith end_time, ith val) 需要找到前i-1 end_time 的最大值，加上ith val, 遍历所有时间，找出最大值。