1차원 직선 위 겹치는 선분들

모든 '교차'하는 선분 쌍에 대한 질의

https://acm-iupc.tistory.com/entry/%EC%84%A0%EB%B6%84%EC%97%90-%EB%8C%80%ED%95%9C-%EC%A7%88%EC%9D%98

 

*교차하는 모든 선분 쌍의 수 nlogn에 구하는 법은 못 찾겠고 생각이 안난다 (20.4.5)

---

겹치는 선분에 대한 생각 정리용 포스트

 

https://www.acmicpc.net/problem/11000

위 문제에서 어떤 시간에 필요한 강의실의 수 = 그 시점에 겹치는 선분의 수

 

 

<좌표 범위가 제한적일 때>

total = 겹치는 선분 쌍의 수

mx = 최대로 겹칠 때 겹치는 선분 수

const int MAX = 2e5 + 4;

int n, ps[MAX],mx, total;
P line[MAX];

int main() {
	FAST; cin >> n;
	for (int i = 0, u, v; i < n; i++) {
		cin >> u >> v;
		ps[u]++, ps[v]--;
		line[i] = { u,v };
	}
	sort(line, line + n);

	for (int i = 1; i <= n; i++) ps[i] += ps[i - 1];

	for (int i = 0, st, en; i < n; i++) {
		tie(st, en) = line[i];
		total += ps[st]-1;
		mx = max(mx, ps[st]);
	}
}

 

 

<좌표 범위에 제한 없을 때>

잘 알려진 우선순위 큐를 활용.

const int MAX = 2e5 + 4;

int n, total, mx;
P line[MAX];

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) cin >> line[i].first >> line[i].second;
	sort(line, line + n);

	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(line[0].second);

	for (int i = 1, st, en; i < n; i++) {
		tie(st, en) = line[i];
		while (!pq.empty() && pq.top() <= st) pq.pop();
		pq.push(en);
		mx = max(mx, (int)pq.size());
		total += (pq.size()-1);
	}

	cout << mx << '\n';
}

 

while문에서 원소를 빼는건 for문 전체에 걸쳐 최대 n번 이뤄지므로 위 알고리즘은 nlogn