AcWing 906. 区间分组
原题链接
简单
作者:
tq
,
2024-04-23 20:20:52
,
所有人可见
,
阅读 4
//第二遍不会,甚至没看懂前面的
//小根堆是重点,这里改了方法是模仿力扣56题的动态二维数组
//一直错的点是把n--减到0了,后面还使用n呢
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 100010;
int main(){
vector<vector<int>> nums;
int n;
scanf("%d", &n);
int k = n;
while(k --){
int a, b;
scanf("%d%d", &a, &b);
nums.push_back({a, b});
}
sort(nums.begin(), nums.end());
priority_queue<int, vector<int>, greater<int>> heap; //小根堆,压栈后自动排序
for(int i = 0; i < n; i ++){
if(heap.empty() || heap.top() >= nums[i][0]) heap.push(nums[i][1]); //空堆或者重叠的话,开新区间
else{
heap.pop(); //不重叠 并列 把之前的右端点弹出 压入新的右端点
heap.push(nums[i][1]);
}
}
printf("%d", heap.size());
return 0;
}