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:
import sys
input = sys.stdin.readline
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])
blue.sort()

ans = 0
red_used = [0 for _ in range(N)]
for b in blue :
    for i in range(N) :
        if b[0] > red[i][0] and b[1] > red[i][1] :
            if red_used[i] == 0 :
                ans += 1
                red_used[i] = 1
                break

print(ans)

Submission status: Accepted

Solution code:
#091_C
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
cd = [tuple(map(int, input().split())) for _ in range(n)]

ab.sort(key = lambda x:(-x[1]))
cd.sort(key = lambda x:(x[0]))
flg = [True for _ in range(n)] 
ans = 0

for i in range(n):
    c, d = cd[i]
    for j in range(n):
        if flg[j]:
            a, b = ab[j]
            if a < c and b < d:
                ans += 1
                flg[j] = False
                break
                
print(ans)

Submission status: Accepted

Solution code:
import copy
n = int(input())
ab = sorted([list(map(int,input().split())) for _ in range(n)],reverse=True)
cd = sorted([list(map(int,input().split())) for _ in range(n)],key = lambda x:x[1])
ans = 0
#print(ab,cd)
for i in range(n):
  for j in range(len(cd)):
    if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
      ans += 1
      cd.remove(cd[j])
      break
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 +7
INF = 10**9

def main():
    n = int(input())
    R = [tuple(map(int,input().split())) for _ in range(n)]
    B = [tuple(map(int,input().split())) for _ in range(n)]
    
    B.sort(key = lambda x:x[0])
    R.sort(key = lambda x:x[1],reverse=True)
    done = [1] * n
    
    cnt = 0
    for i in range(n):
        bx,by = B[i]
        for j in range(n):
            if done[j] and R[j][0] < bx and R[j][1] < by:
                cnt += 1
                done[j] = 0
                break
    
    print(cnt)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n)]
cd = [tuple(map(int,input().split())) for i in range(n)]
ans = 0

ab = sorted(ab,key = lambda x:x[1],reverse = True)
cd.sort()



for (c,d) in cd:
    for (a,b) in ab:
        if a < c and b < d:
            ans += 1
            ab.remove((a,b))
            break
print(ans)

Submission status: Accepted

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

ab = sorted(ab, key= lambda x: [x[0], x[1]])
cd = sorted(cd, key= lambda x: [x[0], x[1]])

kouho = []
ans = 0
temp = 0

used = [False for _ in range(N)]

for i, j in cd:
    for w, kl in enumerate(ab):
        k, l = kl
        if i < k or j < l or used[w] == True:
            continue
        else:
            kouho.append([l, w])
    if len(kouho) != 0:
        kouho = sorted(kouho, key= lambda x: x[0], reverse=True)
        ans += 1
        used[kouho[0][1]] = True
        kouho = []

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = []
for _ in range(n):
  x,y = map(int,input().split())
  p += [(0, x, y)]
for _ in range(n):
  x,y = map(int,input().split())
  p += [(1, x, y)]
  
p = sorted(p, key = lambda x:x[1])
ys = set()
ans = 0
for i in range(2*n):
  if p[i][0] == 0:
    ys.add(p[i][2])
  else:
    yr = p[i][2]
    yb = -1
    for y in list(ys):
      if y < yr:
        yb = max(yb, y)
    if yb != -1:
      ans += 1
      ys.remove(yb)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
r = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]

from operator import itemgetter
r = sorted(r, key=itemgetter(1),reverse=1)
b = sorted(b)

x=0
y=[200,200]
z=[0,0]

for i in range(n):
    for j in range(n):
        if b[i][0] > r[j][0] and b[i][1] > r[j][1]:
            x+=1
            r[j] = y
            b[i] = z
            break

print(x)

Submission status: Accepted

Solution code:
##実装のバグがとれぬ　答えを見る

N = int(input())
ab = []
cd = []
for i in range(N):
    a,b = map(int,input().split())
    ab.append([b,a,i])
for i in range(N):
    c,d = map(int,input().split())
    cd.append([c,d,i])

ab.sort()
cd.sort()

ans = 0
flag_ab = [1]*N
for i in range(N):
    pos = -1
    for j in range(N):
        if ab[j][0] < cd[i][1] and ab[j][1] < cd[i][0] and flag_ab[j]:
            pos = max(pos,j)
    if pos != -1:
        flag_ab[pos] = 0
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input());f=lambda x:sorted([list(map(int,input().split()))for _ in range(n)],key=lambda k:k[x]);r=f(1)[::-1];b=f(0);a=0
for c,d in b:
  for l in r:
    if c>l[0] and d>l[1]:r.remove(l);a+=1;break
print(a)

Submission status: Accepted

Solution code:
n=int(input())
f=lambda x:sorted([list(map(int,input().split())) for _ in range(n)],key=lambda k:k[x])
r,b=f(1)[::-1],f(0)
a=0
for c,d in b:
  for l in r:
    if c>l[0] and d>l[1]: r.remove(l); a+=1; break
print(a)

Submission status: Accepted

Solution code:
n=int(input())
f=lambda x:sorted([list(map(int,input().split())) for _ in range(n)],key=lambda k:k[x])
qr,qb=f(1)[::-1],f(0)
a=0
for c,d in qb:
  for r in qr:
    if c>r[0] and d>r[1]: qr.remove(r); a+=1; break
print(a)

Submission status: Accepted

Solution code:
n=int(input())
f=lambda x:sorted([tuple(map(int,input().split())) for _ in range(n)],key=lambda k:k[x])
qr,qb=f(1)[::-1],f(0)
a=0
for c,d in qb:
  for i in range(n-a):
    if c>qr[i][0] and d>qr[i][1]: qr.pop(i); a+=1; break
print(a)

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))

def main():
    N = int(input())
    rl = []
    bl = []
    mf = Dinic(2 * N + 2)
    for i in range(N):
        mf.add_link(0, i+1, 1)
        mf.add_link(i+N+1, 2*N+1, 1)
    for _ in range(N):
        a, b = map(int, input().split())
        rl.append((a,b))
    for _ in range(N):
        c, d = map(int, input().split())
        bl.append((c, d))
    for i in range(N):
        for j in range(N):
            if rl[i][0] < bl[j][0] and rl[i][1] < bl[j][1]:
                mf.add_link(i+1, j+N+1, 1)
    return mf.max_flow(0, 2*N+1)
print(main())

Submission status: Accepted

Solution code:
n = int(input())

AB = [list(map(int, input().split())) for _ in range(n)]
CD = [list(map(int, input().split())) for _ in range(n)]

Red = sorted(AB, key=lambda x: x[1], reverse = True)
Blue = sorted(CD, key= lambda x: x[0])

ans = 0
for b in Blue:
    for r in Red:
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            Red.remove(r)
            break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = []
cd = []
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    ab.append(tmp)
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    cd.append(tmp)

AB = sorted(ab, key=lambda x: x[1],reverse=True)
CD = sorted(cd, key=lambda x: x[0])

ans = 0
for b in CD:
    for r in AB:
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            AB.remove(r)
            break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

reds = [tuple(map(int, input().split())) for _ in range(n)]
blues = [tuple(map(int, input().split())) for _ in range(n)]

blues.sort(key=lambda x:x[0])
reds.sort(key=lambda x:x[1])

count = 0
for b in blues:
    bx, by = b
    for r in reds[::-1]:
        rx, ry = r
        if bx > rx and by > ry:
            count += 1
            reds.remove(r)
            break

print(count)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
x = [inpl() for i in range(n)]
y = [inpl() for i in range(n)]
x.sort(reverse=True)
y.sort(key = lambda x: x[1])
res = 0
used = set()
for i in range(n):
    a,b = x[i][0], x[i][1]
    for j in range(n):
        c,d = y[j][0], y[j][1]
        if a<c and b<d and not j in used:
            res += 1
            used.add(j)
            break
print(res)

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())
red = []
blue = []
for a, b in zip(*[iter(L[:2*N])]*2):
  red += [(a,b)]
for c, d in zip(*[iter(L[2*N:])]*2):
  blue += [(c,d)]
red.sort(reverse=True)
blue.sort(reverse=True)
S = set(range(N))

ans = 0
for a,b in red:
  k = -1
  m = 10**3
  for j, n in enumerate(blue):
    c,d = n
    if c<a:
      break
    if d-b>0 and d-b<m and j in S:
      k = j
      m = d-b
  if k!=-1:
    ans += 1
    S.remove(k)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
cd = []
for _ in range(n):
    c, d = (int(x) for x in input().split())
    cd.append([c, d])
ab = sorted(ab, key=lambda x: -x[0])
cd = sorted(cd, key=lambda x: x[1])

count = 0

for a, b in ab:
    index = -1
    for i, cda in enumerate(cd):
        if a < cda[0] and b < cda[1] :
            index = i
            break
    if index != -1:
        cd.pop(index)
        count += 1
print(count)

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(key=lambda x: x[0])
used_red = [0]*N
for i in range(N):
    idx = -1
    for j in range(N):
        if used_red[j] != 0:
            continue
        if blue[i][0]-red[j][0]>0 and blue[i][1]-red[j][1]>0:
            if idx == -1 or red[idx][1]<red[j][1]:
                idx = j
    if idx!=-1:
        used_red[idx] += 1

print(sum(used_red))

Submission status: Accepted

Solution code:
# Dinic's algorithm O(VE^2)
from collections import deque


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


n = int(input())
dinic = Dinic(n * 2 + 2)
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
    dinic.add_edge(n*2, i, 1)
    for j in range(n):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            dinic.add_edge(i, j+n, 1)
for i in range(n):
    dinic.add_edge(i+n, n*2+1, 1)
print(dinic.flow(n*2, n*2+1))

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]

cd.sort()
remain = set(range(n))

ans = 0
for c,d in cd:
    cand = [-1, -1]
    for i in remain:
        a,b = ab[i]
        if((a<c) & (b<d)):
            if(cand[1] < b):
                cand = [i,b]

    if(cand[0] == -1):
        continue

    remain.remove(cand[0])
    ans += 1


print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc091/tasks/arc092_a

xが小さい方から見ていく
→青があったら、今まで見た赤の点の内、現在選んでいる点よりy軸が小さく、最大の点を選んで繋げる
→最適性は簡単にわかる

"""
import bisect
N = int(input())

p = []

for i in range(N):

    a,b = map(int,input().split())
    p.append([a,b,0])

for i in range(N):

    c,d = map(int,input().split())
    p.append([c,d,1])

p.sort()

R = []
ans = 0

for i in range(2*N):

    x,y,cl = p[i]

    if cl == 0:
        R.append(y)
        R.sort()

    else:
        ind = bisect.bisect_left(R,y)
        if ind == 0:
            continue
        else:
            del R[ind-1]
            ans += 1
    #print (R)

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
aka = []
ao = []
aka = aka + [list(map(int,input().split())) for _ in range(n)]
ao = ao + [list(map(int,input().split())) for _ in range(n)]

aka = sorted(aka, key=lambda x:x[1],reverse=True)
ao = sorted(ao, key=lambda x:x[0])

ans = 0

for i in range(n):
	for j in range(n):
		if ao[i][0] > aka[j][0] and ao[i][1] > aka[j][1]:
			ans += 1
			aka[j][1] = 201
			break

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

a=[0]*n
b=[0]*n
c=[0]*n
d=[0]*n
edges=[set() for _ in range(n)]
matched=[-1]*n

for i in range(n):
    ta,tb=list(map(int,input().split()))
    a[i]=ta
    b[i]=tb

for i in range(n):
    tc,td=list(map(int,input().split()))
    c[i]=tc
    d[i]=td

for i in range(n):
    for j in range(n):
        if a[i]<c[j] and b[i]<d[j]:
            edges[i].add(j)

def dfs(v,visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u]==-1 or dfs(matched[u],visited):
            matched[u]=v
            return True
    
    return False

print(sum(dfs(s,set()) for s in range(n)))

Submission status: Accepted

Solution code:
X_INDEX = 0
Y_INDEX = 1


def solve():
    number_of_balls = int(input())
    red_points = [list(map(int, input().split())) for _ in range(number_of_balls)]
    blue_points = [list(map(int, input().split())) for _ in range(number_of_balls)]

    from operator import itemgetter
    blue_points.sort(key=itemgetter(X_INDEX))  # 青玉をx座標の昇順でソート
    red_points.sort(key=itemgetter(Y_INDEX), reverse=True)  # 赤玉をy座標の降順でソート

    # 青玉：x座標の小さいものからペアを作っていく
    # 赤玉：青玉のx座標よりも小さいものの中で、y座標が最大のものをペアとする
    number_of_pairs = 0  # 仲良しペアの数
    used_red_points = [False for _ in range(number_of_balls)]  # 使用済み赤玉情報
    # used_blue_points = [False for _ in range(number_of_balls)]  # 使用済み青玉情報
    for blue_i, blue_point in enumerate(blue_points):
        for red_i, red_point in enumerate(red_points):
            if red_point[X_INDEX] < blue_point[X_INDEX] and \
                    red_point[Y_INDEX] < blue_point[Y_INDEX] and \
                    not used_red_points[red_i]:
                number_of_pairs += 1
                used_red_points[red_i] = True
                break

    print(number_of_pairs)


solve()

Submission status: Accepted

Solution code:
INF = float("inf") #const
MOD = 10**9+7 #const
MAX = 510000 #const

import fractions
import itertools

def main():
    n = int(input())
    ab = [list(map(int,input().split())) for _ in range(n)]
    ab = sorted(ab,key=lambda x:x[1],reverse=True)
    cd = [list(map(int,input().split())) for _ in range(n)]
    cd = sorted(cd,key=lambda x:x[0])

    ans = 0
    for blue in cd:
        for red in ab:
            if red[0] < blue[0] and red[1] < blue[1]:
                ans += 1
                red[1] = 201
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    R = [tuple(map(int, ab)) for ab in map(str.split, args[1:n+1])]
    B = [tuple(map(int, ab)) for ab in map(str.split, args[n+1:2*n+1])]

    R.sort(key=lambda x: (-x[1], x[0]))
    B.sort(key=lambda x: (x[0], x[1]))

    count = 0
    used = [False]*n
    for i in range(n):
        bx, by = B[i]
        for j in range(n):
            if used[j]:
                continue
            rx, ry = R[j]
            if rx < bx and ry < by:
                count += 1
                used[j] = True
                break

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
N = int(input())

A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]
A = sorted(A, key=lambda x: -x[1])  # sort by y-axis [max,..., min]
B = sorted(B, key=lambda x: x[0])   # sort by x-axis [min,..., max]

for i in range(N):
    for j in range(len(A)):
        if A[j][0] < B[i][0] and A[j][1] < B[i][1]:
            A.pop(j)
            break

print(N - len(A))

Submission status: Accepted

Solution code:
N = int(input())
R = [list(map(int, input().split())) for n in range(N)]
B = [list(map(int, input().split())) for n in range(N)]

RY = sorted(R, key=lambda x: x[1], reverse=True)
BX = sorted(B, key=lambda x: x[0])

ans = 0

for b in BX:
  for index, r in enumerate(RY):
    if b[0] > r[0] and b[1] > r[1]:
      ans += 1
      RY.pop(index)
      break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
    """
    1-indexed
    din = Dinic(N)
    for _ in range(M):
        s,t,cap = map(int,input().split())
        din.add_edge(s,t,cap)
    ans = din.get_maximumFlow(source, sink)
    """

    def __init__(self, N):
        self.N = N
        self.edge = [[] for _ in range(N + 1)]
        self.level = [-1] * (N + 1)

    def add_edge(self, v_from, v_to, cap):
        self.edge[v_from].append([v_to, cap, len(self.edge[v_to])])
        self.edge[v_to].append([v_from, 0, len(self.edge[v_from]) - 1])

    def _BFS(self, s):
        """
        sからの最短距離をBFSで計算する  
        """
        level = [-1] * (self.N + 1)
        level[s] = 0
        que = deque([s])
        while que:
            s = que.popleft()
            for t, cap, _ in self.edge[s]:
                if cap > 0 and level[t] < 0:
                    level[t] = level[s] + 1
                    que.append(t)
        self.level = level[:]

    def _DFS(self, v, goal, f):
        """
        増加パスをDFSで探す
        """
        if v == goal:
            return f
        for i in range(self.iterate[v], len(self.edge[v])):
            self.iterate[v] = i
            to, cap, rev = self.edge[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self._DFS(to, goal, min(cap, f))
                if d > 0:
                    self.edge[v][i][1] -= d
                    self.edge[to][rev][1] += d
                    return d
        return 0

    def get_maximumFlow(self, s, t):
        """
        s -> tの最大流を求める
        1-indexed
        """
        self.goal = t
        inf = 10**18
        flow = 0
        while True:
            self._BFS(s)
            if self.level[t] < 0:
                return flow
            self.iterate = [0] * (self.N + 1)
            while True:
                f = self._DFS(s, t, inf)
                if f <= 0:
                    break
                flow += f


if __name__ == "__main__":
    N = int(input())
    din = Dinic(2 * N + 10)
    red = [tuple(map(int, input().split())) for _ in range(N)]
    blue = [tuple(map(int, input().split())) for _ in range(N)]

    source = 2 * N + 1
    sink = source + 1

    for i, (xi, yi) in enumerate(red):
        for j, (xj, yj) in enumerate(blue):
            if xi < xj and yi < yj:
                s = i + 1
                t = j + 1 + N
                din.add_edge(s, t, 1)
    for i in range(1, N + 1):
        din.add_edge(source, i, 1)
        din.add_edge(i + N, sink, 1)

    ans = din.get_maximumFlow(source, sink)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
r = [list(map(int, input().split())) for _ in range(n)]
r.sort(key=lambda x: x[1], reverse=True)  # redはyを昇順でソート
b = [list(map(int, input().split())) for _ in range(n)]
b.sort()  # blueはxが降順にソート
cnt = 0  # cntの初期の設定
for i in range(n):  # blueのxが小さい方から全探索
    for j in range(len(r)):
        if r[j][0] < b[i][0] and r[j][1] < b[i][1]:
            cnt += 1
            r.pop(j)
            break
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
R = [tuple(map(int, input().split())) for i in range(N)]
B = [tuple(map(int, input().split())) for i in range(N)]

R.sort(key=lambda r: r[1], reverse=True)
B.sort()

ans = 0
for b in B:
    for r in R:
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            R.remove(r)
            break
print(ans)

Submission status: Accepted

Solution code:
import bisect

N=int(input())
ab=[[0,0,0] for _ in range(N)]#x,y,used
cd=[[0,0,0] for _ in range(N)]

for i in range(N):
    ab[i][0],ab[i][1]=map(int,input().split())

for i in range(N):
    cd[i][0],cd[i][1]=map(int,input().split())
    
    
    
ab.sort()
cd.sort()
ans=0

for i in range(N):#各青に対して，
    temp_j=-1
    temp_y=-1
    for j in range(N):
        if ab[j][2]==0:#未使用ならば
            if ab[j][0] < cd[i][0]: #x座標が小さい中で
                if cd[i][1] > ab[j][1] and ab[j][1]>=temp_y:#y座標が最大のものを選ぶ
                    temp_y=ab[j][1]
                    temp_j=j
    if temp_j!=-1:
        ab[temp_j][2]=1
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    R = [[int(x) for x in input().split()] for i in range(N)]
    B = [[int(x) for x in input().split()] for i in range(N)]
    B.sort()
    selected = set()
    for b in B:
        r_lst = []
        for i in range(len(R)):
            if i in selected: continue
            r = R[i]
            if r[0] < b[0] and r[1] < b[1]:
                r_lst.append(i)
        if len(r_lst) == 0:
            continue
        rym = -1
        rym_i = -1
        for i in r_lst:
            if rym < R[i][1]:
                rym = R[i][1]
                rym_i = i
        selected.add(rym_i)
    return len(selected)
if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
n = int(input())
AB = []
for _ in range(n):
    a, b = map(int, input().split())
    AB.append((a,b))

CD = []
for _ in range(n):
    c, d = map(int, input().split())
    CD.append((c,d))

CD = sorted(CD, key=lambda x:x[1])
count = 0

for cd in CD:
    c = cd[0]
    d = cd[1]
    max_a = -1
    max_b = -1
    for ab in AB:
        a = ab[0]
        b = ab[1]
        if b < d and a < c:
            if max_a < a:
                max_a = a
                max_b = b
    if max_a == -1:
        pass
    else:
        AB.remove((max_a, max_b))
        count += 1

print(count)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  R = [list(map(int, input().split())) for _ in range(n)]
  B = [list(map(int, input().split())) for _ in range(n)]
  
  R = sorted(R, key=lambda p:p[1], reverse=True)
  B = sorted(B)
  ans = 0
  
  for xB, yB in B:
    for xR, yR in R:
      if xR < xB and yR < yB:
        R.remove([xR, yR])
        ans += 1
        break
  print(ans)

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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()
blue.sort()

ans = 0
for c,d in blue:
    x = []
    for a,b in red:
        if a < c and b < d:
            x.append([a,b])
    if len(x) > 0:
        ans += 1
        x = sorted(x, key=lambda x:x[1])
        red.remove(x[-1])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

"""考え方
1.青色を第一要素（x）が小さい順にソートする
2.青色の点より左にある赤い点のうち、yが小さく、かつ一番大きい赤い点を選択する
"""

## 1.必要な配列を取得し、x軸でソートしておく
## 1-1.赤色
AB = []
for n in range(N):
  AB.append(list(map(int, input().split())))
  
AB = sorted(AB, key=lambda x: x[1], reverse=True)

## 1-2.青色
CD = []
for n in range(N):
  CD.append(list(map(int, input().split())))
CD = sorted(CD, key=lambda x: x[0], reverse=False)


## 2.青色の点について、左から順に取得していく
used_idx = []
ans = 0
for _ in CD:
  c = _[0]
  d = _[1]
  red_max_y = -1
  ## 左側にある赤色の要素を検索
  for idx, __ in enumerate(AB):
    a = __[0]
    b = __[1]
    if a < c:
      if b < d:
        if idx not in used_idx:
          used_idx.append(idx)
          ans += 1
          break
  
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red = []
blue = []
B = [0]*(n+1)
for i in range(n):
  red.append(list(map(int,input().split())))

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

for i in range(n):
  for j in range(n):
    if (red[j][0] < blue[i][0] and red[j][1] < blue[i][1]) and B[j+1] == 0:
      B[j+1] = 1
      cnt += 1
      break

print(cnt)

Submission status: Accepted

Solution code:
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[0], reverse=True)
blue.sort(key=lambda x:x[1])
 
ans = 0
for i in range(N):
    a,b = red[i]
    for j in range(len(blue)):
        c,d = blue[j]
        if a < c and b < d:
            blue.pop(j)
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc091/tasks/arc092_a
n = int(input())
coordinates_red = [list(map(int, input().split())) for _ in range(n)]
coordinates_blue = [list(map(int, input().split())) for _ in range(n)]
coordinates_red.sort()
coordinates_blue.sort()
#print(coordinates_red)
#print(coordinates_blue)

start = 0
ans = 0
for blue in coordinates_blue:
    candidate = []
    for red in coordinates_red:
        #print(blue)
        #print(red)
        if red[0] < blue[0] and red[1] < blue[1]:
            candidate.append(red)
    if candidate:
        candidate.sort(key=lambda x: x[1])
        coordinates_red.remove(candidate.pop(-1))
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
r=[tuple(map(int,input().split())) for i in range(N)]
b=[tuple(map(int,input().split())) for i in range(N)]
r.sort()
b.sort()
a=0
for i in b:
    t=(-1,-1)
    for j in r:
        if j[0]>i[0]:
            break
        if t[1]<j[1]<i[1]:
            t=j
    if t!=(-1,-1):
        r.remove(t)
        a+=1
print(a)

Submission status: Accepted

Solution code:
n = int(input())
red = []
blue = []
for _ in range(n):
    red.append(list(map(int, input().split())))
for _ in range(n):
    blue.append(list(map(int, input().split())))

# 赤はy座標が大きい順に取っていくので、yで降順
red.sort(key=lambda x: x[1], reverse=True)
# 青はx座標が小さい順に探していくので、xで昇順
blue.sort()

pair_count = 0
for i in range(n):
    for j in range(len(red)):
        if red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
            pair_count += 1
            red.pop(j)
            break

print(pair_count)

Submission status: Accepted

Solution code:
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)]
r.sort(key=lambda x: x[1], reverse=True)
b.sort(key=lambda x: x[0])
ans = 0
for i, bb in enumerate(b):
    c, d = bb
    for j, rr in enumerate(r):
        a, b = rr
        if c > a and d > b:
            ans += 1
            del r[j]
            break
print(ans)