1689번: 겹치는 선분

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


$O(n\lg n)$

시작 지점에 1, 끝 지점에 -1을 누적 시키고
앞부터 가중치를 더해가면 겹치는 선분 개수를 알 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[2000000];
int r, s, n;
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        p[i] = { x,1 };
        p[i + n] = { y,-1 };
    }
    sort(p, p + 2 * n);
    for (int i = 0; i < 2 * n; i++) {
        s += p[i].second;
        r = max(r, s);
    }
    printf("%d", r);
    return 0;
}