C - 2D Plane 2N Points https://atcoder.jp/contests/abc091/tasks/arc092_a

arc092_a.py

class BipartiteMatching:
    def __init__(self, sl, sr):
        self.__size_left = sl
        self.__size_right = sr
        self.__list = [[] for _ in range(sl)]

    def add_edge(self, l, r):
        self.__list[l].append(r)

    def dfs(self, l, seen):
        if seen[l]:
            return False
        seen[l] = True
        for r in self.__list[l]:
            if self.__r2l[r] == -1 or self.dfs(self.__r2l[r], seen):
                self.__l2r[l] = r
                self.__r2l[r] = l
                return True
        return False

    def solv(self):
        res = []
        self.__l2r = [-1 for _ in range(self.__size_left)]
        self.__r2l = [-1 for _ in range(self.__size_right)]
        while True:
            update = False
            seen = [False for _ in range(self.__size_left)]
            for l in range(self.__size_left):
                if self.__l2r[l] != -1:
                    continue
                if self.dfs(l, seen):
                    update = True
                    break
            if not update:
                break
        for l in range(self.__size_left):
            if self.__l2r[l] != -1:
                res.append([l, self.__l2r[l]])
        return res


N = int(input())
red = []
for i in range(N):
    a, b = map(int, input().split())
    red.append([a, b])
blue = []
for i in range(N):
    c, d = map(int, input().split())
    blue.append([c, d])
bm = BipartiteMatching(N, N)
for i in range(N):
    for j in range(N):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            bm.add_edge(i, j)
print(len(bm.solv()))

二部マッチング問題を解くためのクラス - Mae向きなブログ