AcWing 906. 区间分组
给定N个闭区间[ a i , b i ],请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个整数ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
思路
①将所有区间按左端点从小到大排序
②从前往后处理每个区间
ans为最优解cnt为可行解 ∴ \therefore∴ans<=cnt
而可行解的每个分组里至少有一个区间 可能有多个区间 ∴ \therefore∴ans>=cnt
∴ \therefore∴ ans==cnt
PS:按照左端点从小到大排序 当前区间的左端点≥ \geq≥上一个区间的左端点 如果其左端点≤ \leq≤上一区间右端点 则一定有交点 不能放在一组
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100010; int n; struct Range { int l, r; }range[N]; bool cmp(struct Range a, struct Range b) { return a.l < b.l; } int main() { cin >> n; for (int i = 0; i < n; ++i) { scanf("%d%d", &range[i].l, &range[i].r); } sort(range, range + n, cmp); priority_queue<int, vector<int>, greater<int> >heap; for (int i = 0; i < n; ++i) { auto r = range[i]; if (heap.empty() || heap.top() >= r.l)heap.push(r.r); else { heap.pop(); heap.push(r.r); } } cout << heap.size() << endl; return 0; }
