Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for l in range(N)]
B = [list(map(int,input().split())) for l in range(N)]
A.sort()
B.sort()
for i in range(N):
    a = -5
    b = -1
    for j in range(len(A)):
        if A[j][0]<B[i][0] and A[j][1]<B[i][1]:
           if a<A[j][1]:
              a = A[j][1]
              b = j
    if b!=-1:
        del A[b]
print(N-len(A))

Submission status: Accepted

Solution code:
n = int(input())
rx = []
bx = []

for i in range(n):
    r = tuple(map(int, input().split()))
    rx.append([r, 0])

for j in range(n):
    b = tuple(map(int, input().split()))
    bx.append([b, 0])

rx.sort(key=lambda x: x[0][1], reverse=True)
bx.sort(key=lambda x: x[0][0])

ans = 0

for i in range(n):
    for j in range(n):
        if rx[j][0][0] < bx[i][0][0] and rx[j][0][1] < bx[i][0][1]:
            if rx[j][1] == 0:
                ans += 1
                rx[j][1] = 1
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def main():
    n = int(input())
    reds = []
    blues = []

    for _ in range(n):
        x, y = map(int, input().split())
        reds.append(Point(x, y))

    for _ in range(n):
        x, y = map(int, input().split())
        blues.append(Point(x, y))
    
    print(solve(reds, blues))

def solve(reds, blues):
    cnt = 0
    r = reds.copy()

    for b in sorted(blues):
        i = find_pair(r, b.x, b.y)
        if i is not None:
            del r[i]
            cnt += 1
        pass
    
    return cnt

def find_pair(reds, x, y):
    t = None
    for i, p in enumerate(reds):
        if p.x < x and p.y < y:
            if t is None:
                t = i
            elif p.y > reds[t].y:
                t = i
    return t

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator

import queue


inf = float('inf')


# globals
N = 0
A, B, C, D = [], [], [], []


def set_inputs():
    global N, A, B, C, D
    N = get_int()
    A, B = get_data(N, [int, int])
    C, D = get_data(N, [int, int])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    reds = [(a, b) for a, b in zip(A, B)]
    blues = [(c, d) for c, d in zip(C, D)]
    b2r = defaultdict(list)
    for i in range(N):
        for j in range(N):
            a, b = reds[i]
            c, d = blues[j]
            if a < c and b < d:
                b2r[j].append(i)
    r2b = dict()
    for b, rs in sorted(b2r.items(), key=lambda x: blues[x[0]][0]):
        for r in sorted(rs, key=lambda i: reds[i][1], reverse=True):
            if r2b.get(r, None) is None:
                r2b[r] = b
                break
    print(len(r2b.keys()))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
r = [[0, 0]] * n
b = [[0, 0]] * n
f = [[0 for i in range(0, 2 * n + 2)] for j in range(0, 2 * n + 2)]
     
for i in range(0, n):
    r[i] = [int(i) for i in input().split(" ")]
for i in range(0, n):
    b[i] = [int(i) for i in input().split(" ")]
     
for i in range(0, n):
    f[0][2 * i + 1] = 1
    f[2 * i + 2][2 * n + 1] = 1
    for j in range(0, n):
        if r[i][0] < b[j][0] and r[i][1] < b[j][1]:
            f[2 * i + 1][2 * j + 2] = 1
    
d = [-1] * (2 * n + 2)
def trav(i):
    global f
    global n
    global d
    if i == 2 * n + 1:
        return True
    else:
        for j in range(0, 2 * n + 2):
            if d[j] < 0 and f[i][j] > 0:
                d[j] = i
                if trav(j):
                    return True
        return False
    
c = 0
while True:
    d = [-1] * (2 * n + 2)
    t = trav(0)
    if t:
        k = 2 * n + 1
        m = 100**2
        k = 2 * n + 1
        while k > 0:
            f[d[k]][k] -= 1
            f[k][d[k]] += 1
            k = d[k]
        c += 1
    else:
        break

print(c)

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(i) for i in input().split()] for i in range(N)]
cd = [[int(i) for i in input().split()] for i in range(N)]
abm = [0]*N
ans = 0

ab.sort()
cd.sort()

for i in cd:
  temp = -1
  ind = 0
  for index,j in enumerate(ab):
    if i[0] > j[0] and i[1] > j[1] > temp and abm[index] == 0:
      temp = j[1]
      ind = index
  if temp > -1:
    ans += 1
    abm[ind] = 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching
・二部最大マッチング
"""

class BipartiteMatching:
    """
    XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
    edges[x]: xとつながるYの頂点のset
    match1[x]: xとマッチングされたYの頂点
    match2[y]: yとマッチングされたXの頂点
    """

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.edges = [set() for _ in range(n)]
        self.match1 = [-1] * n
        self.match2 = [-1] * m
 
    def dfs(self, v, visited):
        """
        :param v: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)
            if self.match2[u] == -1 or self.dfs(self.match2[u], visited):
                self.match2[u] = v
                self.match1[v] = u
                return True
        return False
    
    def add(self, a, b):
        self.edges[a].add(b)

    def whois1(self, a):
        """ :param: グループ1の頂点 :return: ペアになるグループ2の頂点 """
        return self.match1[a]

    def whois2(self, a):
        """ :param: グループ2の頂点 :return: ペアになるグループ1の頂点 """
        return self.match2[a]

    def solve(self):
        # 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
        return sum(self.dfs(i, set()) for i in range(self.n))


N = int(input())
aN, bN, cN, dN = [0] * N, [0] * N, [0] * N, [0] * N
# 赤い点
for i in range(N):
	aN[i], bN[i] = map(int, input().split())
# 青い点
for i in range(N):
	cN[i], dN[i] = map(int, input().split())

# (赤い点の数, 青い点の数)
bm = BipartiteMatching(N, N)
for i in range(N):
	for j in range(N):
		if aN[i] < cN[j] and bN[i] < dN[j]:
			# ペア候補として適切な組を追加していく(0-indexed)
			bm.add(i, j)
print(bm.solve())

Submission status: Accepted

Solution code:
N = int(input())
a, b = [], []
for i in range(N):
    a.append(list(map(int, input().split())))
for i in range(N):
    b.append(list(map(int, input().split())))
b.sort()
ans = 0
ls = []
for y in b:
    c = []
    for x in a:
        if x[0] < y[0] and x[1] < y[1] and not x in ls:
            c.append(x)
    if len(c) != 0:
        c.sort(reverse=True, key=lambda x: x[1])
        ls.append(c.pop(0))
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a, b = [], []
for i in range(N):
    a.append(list(map(int, input().split())))
for i in range(N):
    b.append(list(map(int, input().split())))
b.sort()
ans = 0
ls = []
for y in b:
    c = []
    for x in a:
        if x[0] < y[0] and x[1] < y[1] and not x in ls:
            c.append(x)
    if len(c) != 0:
        c.sort(key=lambda x: x[1], reverse=True)
        ls.append(c.pop(0))
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
rps = [tuple(map(int,input().split())) for _ in range(N)]
bps = [tuple(map(int,input().split())) for _ in range(N)]

bps.sort()
rps.sort(key=lambda x:x[1],reverse=True)

count = 0
for bp in bps:
    for i,rp in enumerate(rps):
        if rp[0] < bp[0] and rp[1] < bp[1]:
            count += 1
            rps.pop(i)
            break

print(count)

Submission status: Accepted

Solution code:
INF = 10**4
n = int(input())

ab = [[int(item) for item in input().split()] for _ in range(n)]
cd = [[int(item) for item in input().split()] for _ in range(n)]

ab.sort(key=lambda x: x[0])
cd.sort(key=lambda x: x[0])

count = 0
for c, d in cd:
  index = -1
  for i, (a, b) in enumerate(ab):
    if a < c and b < d:
      if index == -1:
        index = i
      if ab[index][1] < ab[i][1]:
        index = i
  if index != -1:
    ab[index] = [INF, INF]
    count += 1
print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
  k=list(map(int,input().split()))
  a.append(k)
a.sort()
a.reverse()
for i in range(n):
  k=list(map(int,input().split()))
  b.append(k)
b.sort()
ans=0
for i in range(n):
  c=[]
  for j in range(len(b)):
    if a[i][0]<b[j][0] and a[i][1]<b[j][1]:
      c.append(b[j][1])
    else:
      c.append(10**18)
  if c.count(10**18)!=len(c):
    b.pop(c.index(min(c)))
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

red = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[1], reverse=True)
blue = sorted([list(map(int, input().split())) for i in range(N)])
ans = 0

for b_x, b_y in blue:
    for r_x, r_y in red:
        if b_x > r_x and b_y > r_y:
            red.remove([r_x, r_y])
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

red = [list(map(int, input().split())) for i in range(N)]
blue = [list(map(int, input().split())) for i in range(N)]
red.sort(key=lambda x: x[1], reverse=True)
blue.sort()
ans = 0

for b_x, b_y in blue:
    for r_x, r_y in red:
        if b_x > r_x and b_y > r_y:
            red.remove([r_x, r_y])
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
class FordFulkerson:
    def __init__(self,n):
        self.visited=[False]*n
        self.G=[[0]*n for _ in range(n)]
        self.n=n
    def add_edge(self,fr,to,cap):
        self.G[fr][to]=cap
    def dfs(self,start,goal,f):
        if start==goal:
            return f
        self.visited[start]=True
        for i in range(self.n):
            if i==start:
                continue
            if (not self.visited[i]) and self.G[start][i]>0:
                d=self.dfs(i,goal,min(f,self.G[start][i]))
                if d>0:
                    self.G[start][i]-=d
                    self.G[i][start]+=d
                    return d
        return 0
    def maxflow(self,source,sink):
        flow=0
        while True:
            self.visited=[False]*self.n
            f=self.dfs(source,sink,float('inf'))
            if f==0:
                break
            flow+=f
        return flow

def BipartiteMatching(Pairs,a,b):
    solver=FordFulkerson(a+b+2)
    for x,y in Pairs:
        solver.add_edge(x+1,a+y+1,1)
    for x in range(a):
        solver.add_edge(0,x+1,1)
    for y in range(b):
        solver.add_edge(a+y+1,a+b+1,1)
    return solver.maxflow(0,a+b+1)

N = int(input())
R = [list(map(int,input().split())) for i in range(N)]
B = [list(map(int,input().split())) for i in range(N)]
Pairs = []
for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1]<B[j][1]:
            Pairs.append((i,j))
print(BipartiteMatching(Pairs,N,N))

Submission status: Accepted

Solution code:
n = int(input())
red = sorted(list(map(int, input().split())) for _ in range(n))
blue = sorted(list(map(int, input().split())) for _ in range(n))
red = sorted(red, key = lambda x:x[1])
red_used = []
pair = 0

for i in range(n):
    for j in range(n):
        if blue[i][0] > red[n-1 - j][0] and blue[i][1] > red[n-1 - j][1] and j not in red_used:
            pair += 1
            red_used.append(j)
            break

print(pair)

Submission status: Accepted

Solution code:
n = int(input())
Red = [list(map(int,input().split())) for i in range(n)]
Blue = [list(map(int,input().split())) for i in range(n)]
Red.sort(key=lambda x:x[1], reverse=True)
Blue.sort()
cnt = 0
for b in Blue:
	for r in Red:
		if b[0] > r[0] and b[1] > r[1] :
			cnt += 1
			r[0] = 10**9
			r[1] = 10**9
			break
print(cnt)

Submission status: Accepted

Solution code:
#escape_sequence
#escape_ck_ans
N=int(input())
#red=list(map(int,input().split()))
#blue=list(map(int,input().split()))
red=[list(map(int,input().split())) for i in range(N)]
blue=[list(map(int,input().split())) for i in range(N)]
blue.sort(key=lambda x:x[0])
red.sort(key=lambda x:x[1],reverse=True)
#print(blue)
#print(red)
pairs=0
flag=[True for i in range(N)]
for i in range(N):#blue
    for j in range(N):#red
        if blue[i][0]>red[j][0] and blue[i][1]>red[j][1] and flag[j]==True:
            pairs+=1
            flag[j]=False#used_red
            break
print(pairs)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N = I()
A,B = [], []
for n in range(N):
    A.append(LI())
for n in range(N):
    B.append(LI())

#  N = 100
#  A,B = [], []
#  for n in range(N):
#      A.append([random.randint(0,2*N), random.randint(0, 2*N)])
#  for n in range(N):
#      B.append([random.randint(0,2*N), random.randint(0, 2*N)])

B = sorted(B, key=lambda x: x[0])

result = 0
for b in B:
    tmp = [a for a in A if a[0] < b[0] and a[1] < b[1]]
    if not tmp:
        continue
    result += 1
    closest = max(tmp, key=lambda x: x[1])
    A.remove(closest)
print(result)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


n = int(input())
red = [[0 for j in range(2)] for i in range(n)]
blue = [[0 for j in range(2)] for i in range(n)]
for i in range(n):
  red[i] = list(map(int, input().split()))
for i in range(n):
  blue[i] = list(map(int, input().split()))
blue = sorted(blue)
red = sorted(red,key=lambda x:x[1])
ans = 0
for a,b in blue:
  i = 0
  idx = -1
  while i < len(red):
    if a > red[i][0] and b > red[i][1]:
      idx = max(idx,i)
    i += 1
  if idx >= 0:
    ans += 1
    red.pop(idx)

print(ans)

Submission status: Accepted

Solution code:
def solve(string):
    n, *abcd = map(int, string.split())
    abcd = [(ac, bd) for ac, bd in zip(abcd[::2], abcd[1::2])]
    ab = abcd[:n]

    candidate = []
    ans = 0
    ps = sorted(abcd, key=lambda x: x[0])
    for p in ps:
        if p in ab:
            candidate.append(p)
            candidate = sorted(candidate, key=lambda x: x[1], reverse=True)
        else:
            for i, _p in enumerate(candidate):
                if _p[1] < p[1]:
                    ans += 1
                    candidate.pop(i)
                    break
    return str(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(2 * n)])))

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
for i in range(N):
    a, b = map(int, input().split())
    red.append((a, b))

for i in range(N):
    c, d = map(int, input().split())
    blue.append((c, d))

blue.sort()
red = sorted(red, key=lambda x: x[1])[::-1]
cnt = 0
for i in range(N):
    c, d = blue[i]
    k = -1
    for j in range(len(red)):
        a, b = red[j]
        if a < c and b < d:
            k = j
            break
    if k != -1:
        red.pop(k)
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in range(n):
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in range(n+1):
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])

    n = I()
    r = LIR(n)
    b = LIR(n)
    c = [[0 for i in range(2*n+2)] for i in range(2*n+2)]
    for i in range(n):
        c[0][i+1] = 1
        for j in range(n):
            if r[i][0] < b[j][0] and r[i][1] < b[j][1]:
                c[i+1][n+j+1] = 1
    for j in range(n):
        c[n+j+1][2*n+1] = 1
    print(ford_fulkerson(0,2*n+1,c,2*n+2))
#D
def D():
    n = I()
    a = LI()
    b = LI()
    ans = 0
    p = 1
    for k in range(30):
        s = 0
        c = [b[i]%(p*2) for i in range(n)]
        a_ = [a[i]%(p*2) for i in range(n)]
        c.sort()
        a_.sort()
        l1,l2,l3 = 0,0,0
        y = float("inf")
        for x in a_[::-1]:
            if x != y:
                while l1 < n and c[l1] < p-x:l1 += 1
                while l2 < n and c[l2] < 2*p-x:l2 += 1
                while l3 < n and c[l3] < 3*p-x:l3 += 1
            s += n-l2-l1-l3
            y = x
        ans += (s%2)*p
        p *= 2
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
N = int(input())
Ri = [list(map(int, input().split())) for _ in range(N)]
Bi = [list(map(int, input().split())) for _ in range(N)]

Ri.sort(key=lambda x: x[0], reverse=True)
Bi.sort(key=lambda x: x[1])
found = [False for _ in range(N)]
count = 0

for b in Bi:
    for (i, r) in enumerate(Ri):
        if not found[i] and r[0] < b[0] and r[1] < b[1]:
            count += 1
            found[i] = True
            break
print(count)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    ab = LIR(n)
    cd = LIR(n)
    ab.sort()
    cd.sort()
    check = [0 for i in range(n)]
    ans = 0
    #print(ab)
    for i, c in enumerate(cd):
        d = c[1]
        c = c[0]
        maxy = -1
        x = -1
        for k, a in enumerate(ab):
            b = a[1]
            a = a[0]
            if maxy < b and c > a and check[k] == 0 and d > b:
                maxy = b
                x = k
                #print(a,b,c,d)
        if x != -1:
            ans += 1
            check[x] += 1
    print(ans)


    return

#D
def D():
    n = II()
    ab = LI()
    cd = LI()
    binab = []
    bincd = []
    warerua = [0 for i in range(28)]
    wareruc = [0 for i in range(28)]
    warenaib = [0 for i in range(28)]
    warenaid = [0 for i in range(28)]
    for i in range(n):
        ab[i] = list(bin(ab[i]))[2:]
        ab[i] = ab[i][::-1]
        cd[i] = list(bin(cd[i]))[2:]
        cd[i] = cd[i][::-1]
    for i in range(n):
        for k in range(len(ab[i])):
            #print(warerua, warenaib, wareruc, warenaid,ab[i][k])
            if ab[i][k] == "1":
                warenaib[k] += 1
            else:
                warerua[k] += 1
        for k in range(len(ab[i]), 28):
            warerua[k] += 1
        for k in range(len(cd[i])):
            if cd[i][k] == "1":
                warenaid[k] += 1
            else:
                wareruc[k] += 1
        for k in range(len(ab[i]), 28):
            wareruc[k] += 1
    ans = 0
    print(warerua, warenaib, wareruc, warenaid)
    for i in range(28):
        kisu = warerua[i] * warenaid[i] + warenaib[i] * wareruc[i]
        gusu = warerua[i] * wareruc[i] + warenaib[i] * warenaid[i]
        if kisu % 2:
            ans += 1 << i
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [-1 for i in range(2*n+2)]
        q = [a]
        bfs_map[a] = 0
        while q:
            x = q.pop(0)
            for y in out[x]:
                if bfs_map[y] == -1:
                    q.append(y)
                    bfs_map[y] = bfs_map[x]+1
        if bfs_map[b] == -1:return 0
        d = bfs_map[b]
        path = [b]
        y = b
        while d > 0:
            for x in ent[y]:
                if bfs_map[x] == d-1:
                    path.insert(0,x)
                    y = x
                    d -= 1
                    break
        return path

    def ford_fulkerson(a,b,c):
        ans = 0
        while 1:
            path = bfs(a,b)
            if not path:break
            for i in range(len(path)-1):
                out[path[i]].remove(path[i+1])
                ent[path[i+1]].remove(path[i])
                if not c[path[i+1]][path[i]]:
                    c[path[i+1]][path[i]] = 1
                    out[path[i+1]].append(path[i])
                    ent[path[i]].append(path[i+1])
            ans += 1
        return ans
    n = I()
    r = LIR(n)
    b = LIR(n)
    c = [[0 for i in range(2*n+2)] for i in range(2*n+2)]
    out = [[] for i in range(2*n+2)]
    ent = [[] for i in range(2*n+2)]
    for i in range(n):
        c[0][i+1] = 1
        out[0].append(i+1)
        ent[i+1].append(0)
        for j in range(n):
            if r[i][0] < b[j][0] and r[i][1] < b[j][1]:
                c[i+1][n+j+1] = 1
                out[i+1].append(n+j+1)
                ent[n+j+1].append(i+1)
    for j in range(n):
        c[n+j+1][2*n+1] = 1
        out[n+j+1].append(2*n+1)
        ent[2*n+1].append(n+j+1)
    print(ford_fulkerson(0,2*n+1,c))
#D
def D():
    n = I()
    a = LI()
    b = LI()
    s = 0
    for i in range(n):
        s ^= b[i]
    ans = 0
    print(s)
    for i in range(n):
        s ^= a[i]
    print(s)

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
from sys import stderr
N = int(input())
red = [tuple(map(int,input().split())) for _ in range(N)]
blue = [tuple(map(int,input().split())) for _ in range(N)]
red.sort(key=lambda x:x[1], reverse=True)
blue.sort()
print(red,file=stderr)
print(blue,file=stderr)

ans = 0
for bx, by in blue:
    for rx, ry in red:
        if rx < bx and ry < by:
            ans += 1
            red.remove((rx,ry))
            break
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())

ab = [[int(j) for j in input().split()] for i in range(N)]

cd = [[int(j) for j in input().split()] for i in range(N)]


def main():
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)

    # x 昇順
    cd.sort(key=itemgetter(0))

    # ペアになった赤
    done = [False] * N

    ans = 0

    for blue in cd:
        i = 0

        for red in ab:
            if not done[i] and red[0] < blue[0] and red[1] < blue[1]:
                done[i] = True
                ans += 1
                break

            i += 1

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin
from operator import itemgetter

input = stdin.readline

N = int(input())

ab = [[int(j) for j in input().split()] for i in range(N)]

cd = [[int(j) for j in input().split()] for i in range(N)]


def main():
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)

    # x 昇順
    cd.sort(key=itemgetter(0))

    # ペアになった赤
    done = [False] * N

    ans = 0

    for blue in cd:
        i = 0

        for red in ab:
            if not done[i] and red[0] < blue[0] and red[1] < blue[1]:
                done[i] = True
                ans += 1
                break

            i += 1

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin
from operator import itemgetter

input = stdin.readline

N = int(input())

ab = [[int(j) for j in input().split()] for i in range(N)]

cd = [[int(j) for j in input().split()] for i in range(N)]


def main():
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)

    # x 昇順
    cd.sort(key=itemgetter(0))

    # ペアになった赤
    done = [False] * N

    ans = 0

    for i in range(N):
        for j in range(N):
            if not done[j] and ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1]:
                done[j] = True
                ans += 1
                break

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

class FordFulkerson:
    def __init__(self,n):
        self.visited=[False]*n
        self.G=[[0]*n for _ in range(n)]
        self.n=n
    def add_edge(self,fr,to,cap):
        self.G[fr][to]=cap
    def dfs(self,start,goal,f):
        if start==goal:
            return f
        self.visited[start]=True
        for i in range(self.n):
            if i==start:
                continue
            if (not self.visited[i]) and self.G[start][i]>0:
                d=self.dfs(i,goal,min(f,self.G[start][i]))
                if d>0:
                    self.G[start][i]-=d
                    self.G[i][start]+=d
                    return d
        return 0
    def maxflow(self,source,sink):
        flow=0
        while True:
            self.visited=[False]*self.n
            f=self.dfs(source,sink,float('inf'))
            if f==0:
                break
            flow+=f
        return flow

def BipartiteMatching(Pairs,a,b):
    solver=FordFulkerson(a+b+2)
    for x,y in Pairs:
        solver.add_edge(x+1,a+y+1,1)
    for x in range(a):
        solver.add_edge(0,x+1,1)
    for y in range(b):
        solver.add_edge(a+y+1,a+b+1,1)
    return solver.maxflow(0,a+b+1)

n=int(input())
R=[list(map(int,input().split())) for _ in range(n)]
B=[list(map(int,input().split())) for _ in range(n)]
Pairs=[]
for i in range(n):
    for j in range(n):
        if R[i][0]<B[j][0] and R[i][1]<B[j][1]:
            Pairs.append((i,j))
print(BipartiteMatching(Pairs,n,n))