문제 풀이

선분들을 오름차순으로 정렬을 먼저 하고, 출발점과 도착점이 작은 선분 부터 순서대로 각각 순회하는데 도착점을 기준으로 도착점보다 출발점이 같거나 크다면 겹치지 않는 것이고, 도착점보다 출발점이 작다면 겹치는 선분이다.
출발점과 도착점이 작은 순서대로 순회하기 때문에 앞으로 순회할 선분에서는 현재 선분의 출발점보다 도착점이 더 작은 선분은 없다!

문제 링크

boj/1689

소스코드

PS/1689.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	
	priority_queue<int> pq;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({a,b });
	}
	sort(v.begin(), v.end());
	pq.push(-v[0].second);
	int ans = 1;
	for (int i = 1; i < v.size(); i++)
	{
		while (!pq.empty() && -pq.top() <= v[i].first)
		{
			pq.pop();
		}
		pq.push(-v[i].second);
		ans = max(ans, (int)pq.size());
	}
	cout << ans;
	
}