https://ac.nowcoder.com/acm/contest/22904/1010
思路来源：
https://www.cnblogs.com/BlankYang/p/16459928.html
@空白菌
思路描述：
-
输入处理：给定
n个用户编号从 1 到n，以及m条服务线，每条服务线对应一个用户区间[l, r]和一个最大容量v，表示这条服务线可以为最多v个用户提供服务，且仅能为用户编号在[l, r]范围内的用户提供服务。 -
排序服务线：将所有服务线按照它们的左端点
l进行排序。这样可以确保在处理每个用户时，按顺序检查该用户可能匹配的服务线。 -
优先队列维护当前可用服务线：使用一个优先队列（最小堆）来维护当前能够为用户提供服务的服务线。优先队列中存储服务线的右端点
r和剩余的可用容量v，并按照右端点r进行排序。这样可以确保我们优先使用那些右端点较小、即将失效的服务线。 -
逐个处理用户：
- 对于每个用户
i，首先移除那些右端点小于i的服务线，因为它们已经不能再为当前及后续用户提供服务了。 - 检查用户
i是否处于某些服务线的左端点l，如果是，将这些服务线加入优先队列，因为这些服务线可以开始为用户提供服务。 - 如果优先队列中还有可用服务线，则为当前用户选择右端点最小的服务线进行分配，并减少该服务线的剩余容量。如果服务线的容量未用完，则将其重新放回优先队列，以便后续用户继续使用。
- 对于每个用户
-
最大化服务用户数量：通过上述操作，逐个处理每个用户，尽可能多地为用户分配可用的服务线，最终统计能够服务的用户数量。
-
输出结果：处理完所有用户后，输出可以服务的最大用户数量。
这种方法确保了我们以贪心策略优先分配即将过期的服务线，同时利用优先队列高效维护可用服务线的信息，从而在尽量少的计算代价下，最大化能够服务的用户数量。
#include <bits/stdc++.h>
using namespace std;
struct Cable {
int l, r, v;
Cable(int l_, int r_, int v_) {
l = l_;
r = r_;
v = v_;
}
};
// 比较函数，用于根据左端点l排序
bool compare(Cable a, Cable b) {
return a.l < b.l;
}
int main() {
int n, m;
// 读入n（用户数量）和m（服务线数量）
while (scanf("%d %d", &n, &m) != EOF) {
vector<Cable> a;
// 读入每条服务线的信息
for (int i = 0; i < m; i++) {
int l, r, v;
scanf("%d %d %d", &l, &r, &v);
a.push_back(Cable(l, r, v));
}
// 按照服务线的左端点l进行排序
sort(a.begin(), a.end(), compare);
// 使用小根堆，存储右端点r和剩余可容纳用户数量v
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int ans = 0;
int pos = 0; // 用来跟踪当前处理的服务线
// 遍历每一个用户编号（从1到n）
for (int i = 1; i <= n; i++) {
// 移除不再覆盖当前用户编号i的服务线（即右端点小于i的）
while (!pq.empty() && pq.top().first < i) {
pq.pop();
}
// 将当前用户编号i对应的新服务线加入到堆中
while (pos < m && a[pos].l == i) {
pq.push({a[pos].r, a[pos].v});
pos++;
}
// 如果当前有可用的服务线，分配用户
if (!pq.empty()) {
ans++;
auto temp = pq.top();
pq.pop();
temp.second--; // 当前服务线容纳量减少1
// 如果服务线还未用完，重新加入堆
if (temp.second > 0) {
pq.push(temp);
}
}
}
// 输出最大在线用户数
printf("%d\n", ans);
}
return 0;
}