해결 방법 1

보조정리: 이분 그래프의 두 부분집합을 각각 X, Y(|X| ≤ |Y|)라고 할 때, 완벽한 매칭이 존재할 필요충분조건은 ∀S ⊆ X, f(S) ≥ |S| (여기서 f(S)는 S와 연결된 점들의 집합)이다. (즉, 홀의 정리)

문제에서 요구하는 것은 기본적으로 완벽한 매칭을 구성하기 위해 최소 몇 개의 의자를 추가해야 하는지를 묻고 있습니다.

따라서 모든 사람이 의자를 선택할 수 있도록 의자를 추가하는 것이 최적이므로, 홀의 정리에 따라 우리가 구해야 하는 것은 maxS⊆X{|S| - |f(S)|}가 됩니다. 이는 maxS⊆X |S| - ⋃i∈S[0, li] ∪ [ri, m]과 같습니다.

합집합은 처리하기 어렵기 때문에, 전체 집합이 주어졌을 때 보수 집합의 교집합을 구하는 것으로 접근할 수 있습니다: maxS⊆X |S| + ⋂i∈S[li, ri] - m.

점 집합을 직접 열거하기는 어렵지만, 구간을 열거할 때 특정 구간을 포함하는 점의 개수를 세는 것은 매우 효율적입니다.

먼저 각 위치에 포함된 오른쪽 끝점과 왼쪽 끝점의 개수를 미리 처리한 후, 포함-배제 원리를 사용한 접두사 합을 통해 O(n + m²) 시간에 해결할 수 있습니다.

이 과정을 최적화하기 위해, 왼쪽 끝점 l만 열거하고 동적으로 왼쪽 끝점이 l보다 작은 점들의 집합이 각 오른쪽 끝점에 대한 답에 미치는 영향을 유지할 수 있습니다.

왼쪽 끝점이 이동할 때 구간 덧셈과 구간 최댓값을 지원해야 하므로 세그먼트 트리를 사용할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
struct Interval { int left, right;} intervals[N];
int n, m, result;
int read() {
    char c; int x = 0, sign = 1;
    c = getchar();
    while (c > '9' || c < '0') { if(c == '-') sign = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * sign;
}
namespace SegmentTree {
    #define left_child (p << 1)
    #define right_child (p << 1 | 1)
    #define mid ((l + r) >> 1)
    struct Node { int max_val, lazy;} tree[N << 2];
    void apply_lazy(int p, int value) { tree[p].max_val += value; tree[p].lazy += value;}
    void update_up(int p) { tree[p].max_val = max(tree[left_child].max_val, tree[right_child].max_val);}
    void push_down(int p) { apply_lazy(left_child, tree[p].lazy), apply_lazy(right_child, tree[p].lazy); tree[p].lazy = 0;}
    void build(int p, int l, int r) {
        if(l == r) { tree[p].max_val = l; return ;}
        build(left_child, l, mid), build(right_child, mid + 1, r);
        update_up(p);
    }
    void range_update(int p, int l, int r, int x, int y, int k) {
        if(x > y) return ;
        if(l >= x && r <= y) { apply_lazy(p, k); return ;}
        push_down(p);
        if(mid >= x) range_update(left_child, l, mid, x, y, k);
        if(mid < y) range_update(right_child, mid + 1, r, x, y, k);
        update_up(p);
    }
    int range_query(int p, int l, int r, int x, int y) {
        if(x > y) return 0;
        if(l >= x && r <= y) return tree[p].max_val;
        push_down(p); int ans = 0;
        if(mid >= x) ans = max(ans, range_query(left_child, l, mid, x, y));
        if(mid < y) ans = max(ans, range_query(right_child, mid + 1, r, x, y));
        return ans;
    }
}
bool compare_intervals(Interval a, Interval b) { return a.left == b.left ? a.right > b.right : a.left < b.left;}
int main() {
    n = read(), m = read() + 1;
    rep(i, 1, n) intervals[i].left = read() + 2, intervals[i].right = read();
    SegmentTree::build(1, 1, m);
    sort(intervals + 1, intervals + n + 1, compare_intervals);
    rep(i, 1, n) {
        if(intervals[i].left > m || intervals[i].left > intervals[i].right) { result = max(result, n - m + 1); continue;} 
        SegmentTree::range_update(1, 1, m, 1, min(intervals[i].right, m), 1);
        result = max(result, SegmentTree::range_query(1, 1, m, intervals[i].left, m) - intervals[i].left - m + 2);
    }
    printf("%d", result);
    return 0;
}

해결 방법 2

특수한 경우에서 출발하여, 만약 오직 왼쪽 끝점의 제약만 존재한다면, 모든 사람을 왼쪽 끝점이 작은 순서대로 정렬하고 현재 선택된 가장 앞 위치를 유지하면서 탐욕적으로 선택하면 됩니다.

이때 오른쪽 끝점의 제약이 추가되면, 위의 탐욕 알고리즘을 조정할 수 있습니다.

먼저 왼쪽 끝점을 기준으로 정렬하고, 가능한 한 선택합니다.

선택할 수 없는 경우가 발생하면, j가 이전에 선택된 사람 중 하나를 대체하여 답을 변경하지 않을 수 있습니다. 하지만 모든 경우에서 대체가 가능한 것은 아닙니다.

더 자세히 관찰하면, 이전에 선택된 i의 ri < rj라면 j가 i를 대체하는 것이 항상 더 나은 선택입니다. 왜냐하면 i를 오른쪽에 남겨두는 가능성이 j보다 크기 때문입니다. 동시에 이 가능성을 최대화하기 위해, 항상 ri가 가장 작은 i를 대체해야 하므로 최소 힙을 사용하여 관리할 수 있습니다.

마지막으로, 오른쪽에 배치해야 하는 시퀀스를 얻을 수 있으며, 이때는 오직 오른쪽 끝점의 제약만 남아 있으므로 처음의 탐욕 알고리즘을 바로 적용할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
struct Interval { int left, right;} intervals[N];
int n, m, current_pos, cnt, right_bounds[N];
priority_queue <int, vector <int>, greater <int> > min_heap;
bool compare_by_left(Interval a, Interval b) { return a.left < b.left;}   
bool compare_descending(int a, int b) { return a > b;}
int main() {
    cin >> n >> m;
    rep(i, 1, n) cin >> intervals[i].left >> intervals[i].right;
    sort(intervals + 1, intervals + n + 1, compare_by_left);
    current_pos = 1;
    rep(i, 1, n) {
        if(current_pos <= intervals[i].left) ++current_pos, min_heap.push(intervals[i].right);
        else {
            if(!min_heap.empty() && intervals[i].right > min_heap.top()) 
                right_bounds[++cnt] = min_heap.top(), min_heap.pop(), min_heap.push(intervals[i].right);
            else right_bounds[++cnt] = intervals[i].right;
        }
    }
    sort(right_bounds + 1, right_bounds + cnt + 1, compare_descending);
    int left_limit = current_pos, right_pos = m;
    rep(i, 1, cnt) if(right_pos >= right_bounds[i] && right_pos >= left_limit) --right_pos;
    printf("%d", n - (m - right_pos + left_limit - 1));
    return 0;
}

해결 방법 1에서는 여러 번 '어렵다면 반대로'하는 사고 방식을 사용했으며, 이는 문제 해결의 핵심 포인트입니다.

해결 방법 2에서는 제약 조건을 완화하고 문제를 특수화한 후 조정하여 원래 문제에 적응시키는 접근법을 사용했습니다.