https://www.hackerrank.com/contests/w4/challenges/crush
第一眼觉得要用线段树,但据说会超时。其实这个可以通过生成pair排序来做。
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream> using namespace std; int main() {
int N, M;
cin >> N >> M;
vector<pair<int, int>> vec;
for (int i = 0; i < M ;i++) {
int a, b, k;
cin >> a >> b >> k;
vec.push_back(make_pair(a, k));
vec.push_back(make_pair(b + 1, -k));
}
sort(vec.begin(), vec.end());
long long max_val = 0;
long long cur_val = 0;
for (int i = 0; i < M * 2; i++) {
cur_val += vec[i].second;
max_val = max(max_val, cur_val);
}
cout << max_val << endl;
return 0;
}