11000번: 강의실 배정

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


$O(n\lg n)$

모든 강의에 대해 [시작,끝) 구간을 나타내는 선분을 만들어보자.
앞에서부터 라인 스위핑을 할 때, 최대로 교차되는 선분 개수가 답이다.

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