13160번: 최대 클리크 구하기

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


$O(nlgn)$

가장 많이 겹치는 지점을 찾는다. 해당하는 선분 집합은 클리크를 이룬다.

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