2D Plane 2N Points [AtCoder Regular Contest 092 C]

https://beta.atcoder.jp/contests/arc092/tasks/arc092_a

前提知識

• 二部最大マッチング

解法

https://beta.atcoder.jp/contests/arc092/submissions/2217043

二部最大マッチングをすれば答えが得られる。
聞き馴染みが無いかも知れないが、最大マッチング問題はよく出てくる題材である。
各マッチングの計算方法は知っておくと良い。
　
これを知らなくても貪欲に取っていく方法が解説放送で紹介されている。
400点問題で最大マッチングを要求するとは思えないので、想定解ではないなと思ってはいたが、貪欲法は細部を詰める必要があるので、今後のためにも最大マッチングも知っていることをおすすめする。
（貪欲法こそ練習する必要がありそうですけど）

int N, A[101], B[101], C[101], D[101];
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    rep(i, 0, N) cin >> C[i] >> D[i];
 
    BipartiteMatching bm;
    bm.init(N, N);
    rep(i, 0, N) rep(j, 0, N) {
        if (A[i] < C[j] and B[i] < D[j]) bm.add(i, j);
    }
    cout << bm.solve() << endl;
}