预处理,可以y总解法时间复杂度降低一个logn级别
class Solution {
public:
typedef pair<int,int> pii;
int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(),events.end(),[](auto &a,auto &b){
return a[1]<b[1];
});
int n=events.size();
set<pii> h;
vector<int> bef(n);
h.insert({events[0][1],1});
for (int i=1;i<n;i++){
auto p=h.upper_bound({events[i][0],-1e9});
if (p!=h.begin()){
p--;
bef[i]=(*p).second;
}
h.insert({events[i][1],i+1});
}
vector<vector<int>> f(n+1,vector<int>(k+1));
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++){
f[i][j]=max(f[i-1][j],f[bef[i-1]][j-1]+events[i-1][2]);
}
return f[n][k];
}
};