题解 | #线段重合#

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n;
struct line
{
	int l;
	int r;
}lin[100005];//用结构体存储线段，方便排序

bool cmp(line l1,line l2)//按线段左端点升序排序
{
	return l1.l < l2.l;
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>lin[i].l>>lin[i].r;
		
	sort(lin,lin+n,cmp);
	priority_queue<int, vector<int>, greater<int>> que;//优先队列模拟小根堆
	int ans=1;
	
	for(int i=0;i<n;i++)
	{
	  //将小根堆里面小于等于<= 第i条线段的左端点l 的值去除
		while(!que.empty() && que.top() <= lin[i].l)//注：!que.empty()应放在前面，否则段错误
			que.pop();
		
		que.push(lin[i].r);//插入第i条线段的右端点
		int res=que.size();//小根堆（优先队列）的大小即为重合的线段条数
		ans=max(ans,res);//取大的
	}
	cout<<ans;
}