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:
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())
ab = []
cd = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append([i+1, a, b])

for i in range(n):
    c, d = map(int, input().split())
    cd.append([n+1+i, c, d])

s = 0
g = 2 * n + 1
edge = []
for i in range(1, n + 1):
    edge.append([0, i])
for i in range(n + 1, g):
    edge.append([i, g])


for i in range(len(ab)):
    i_idx, a, b = ab[i]
    for j in range(len(cd)):
        j_idx, c, d = cd[j]
        if a < c and b < d:
            edge.append([i_idx, j_idx])

try:
    dinic = Dinic(len(edge))

    for i in range(len(edge)):
        dinic.add_edge(edge[i][0], edge[i][1], 1)
    ans = dinic.flow(s, g)

    print(ans)
except:
    print(0)

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

ab.sort()
cd.sort()
num = 0
for i in range(N):
	blue = cd[i]
	red_y_max = -1
	index = -1
	for j in range(N):
		if ab[j][0] > blue[0]:
			break
		if ab[j][1] > red_y_max and ab[j][1] < blue[1]:
			red_y_max = ab[j][1]
			index = j
	if index != -1:
		ab[index][1] = 100000000000
		num += 1
print(num)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for i in range(N):
  a, b = map(int, input().split())
  A.append([a, b])
for i in range(N):
  a, b = map(int, input().split())
  B.append([a, b])
A = sorted(A, key=lambda x: (-x[1]))
B = sorted(B, key=lambda x: (x[0]))
count = 0
for i in range(len(B)):
  for j in range(len(A)):
    if A[j][0] < B[i][0] and A[j][1] < B[i][1]:
      A = A[:j] + A[j+1:]
      count += 1
      break
print(count)

Submission status: Accepted

Solution code:
import sys
INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
LIST = lambda: list(map(int, INPUT().split()))
sys.setrecursionlimit(10 ** 9)


def main():
    N = INT()
    AB = sorted([LIST() for _ in range(N)], key=(lambda x: -x[1]))
    CD = sorted([LIST() for _ in range(N)])

    cnt = 0
    for c, d in CD:
        for a, b in AB:
            if a < c and b < d:
                AB.remove([a, b])
                cnt += 1
                break

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

AB = [[int(_) for _ in input().split()] for i in range(N)]
CD = [[int(_) for _ in input().split()] + [0, ] for i in range(N)]
AB.sort(reverse=True)
CD.sort(reverse=True)
ans = 0
for a, b in AB:
    # for c, d, f in CD:
    min_idx = -1
    min_val = 1e10

    for i in range(N):
        c, d, f = CD[i]
        if f: continue
        if c <= a and d <= b: break
        if c <= a or d <= b: continue
        if min_val > d:
            min_val = d
            min_idx = i
    if min_idx >= 0:
        ans += 1
        CD[min_idx][2] = 1
        #print('pare:', (a, b), CD[min_idx])
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.sort(key=lambda x:(x[1],x[0]),reverse=True)
cd.sort()

ans=0
for i in range(len(cd)):
  for j in range(len(ab)):
    c,d=cd[i]
    a,b=ab[j]
    if int(a)<int(c) and int(b)<int(d):
      ans+=1
      ab.pop(j)
      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)]

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

count = 0
for c, d in CD:
    for j, (a, b) in enumerate(AB):
        if a < c and b < d:
            count += 1
            AB.pop(j)
            break

print(count)

Submission status: Accepted

Solution code:
import heapq

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

ab.sort(reverse=True)
cd.sort(reverse=True)

#print(ab,cd)

hq = []
tmp = 0
ans = 0

for i in range(n):
    while tmp <= n-1 and ab[i][0] < cd[tmp][0]:
        hq.append(cd[tmp][1])
        hq.sort()
        tmp += 1
    #print(hq)
    if len(hq) > 0:
        for j in range(len(hq)):
            if hq[j] > ab[i][1]:
                del hq[j]
                ans += 1
                break
            """
            elif hq[j] <= ab[i][1]:
                break
            else:
                continue
            """
        
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    A[i] = (a, b)

for j in range(N):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    B[j] = (a, b)

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

ans = 0
for k in B:
    flag = False
    val = 0
    max_v = 0
    for l in A:
        if l[0] < k[0] and l[1] < k[1]:
            if max_v <= l[1]:
                flag = True
                max_v = l[1]
                val = l
    if flag:
        ans += 1
        A.remove(val)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
d = [0] * N 
B = [0] * N
for i in range(N):
    A[i] = list(map(int, input().split()))
    d[i] = A[i][1]
for i in range(N):
    B[i] = list(map(int, input().split()))

B.sort()

tmp = []

for i in range(N):
    t = -10
    for j in range(N):
        if A[j][0] < B[i][0] and A[j][1] < B[i][1] and j not in tmp:
            t = max(t, A[j][1]) 
    if t > -1 :
        tmp.append(d.index(t))
    #print(t)

ans = len(tmp)
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[1])
cd.sort()
  
count = 0
for i in range(N):
  idx = -1
  for j in range(len(ab)):
    if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
      idx = j
  if idx >= 0:
    count += 1
    ab.pop(idx)
  
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
A = [tuple(map(int,input().split())) for i in range(N)]
B = [tuple(map(int,input().split())) for i in range(N)]
A.sort()
B.sort()
num = 0
for i in range(N):
    K = [A[k] for k in range(len(A)) if (A[k][0] <B[i][0]) and (A[k][1] < B[i][1])]
    if K:
        num += 1
        t = sorted(K, key=itemgetter(1))[-1]
        A.remove(t)
print(num)

Submission status: Accepted

Solution code:
from operator import itemgetter

def main():
    N = int(input())
    
    red = [[int(i) for i in input().split()] for i in range(N)]
    blue = [[int(i) for i in input().split()] for i in range(N)]

    # 青よりx,y座標のが小さい赤の中で、最もyが大きいものから削除するため
    # 青はxでソート、赤はyで大きい順でソートする
    sort_red = sorted(red, key=itemgetter(1), reverse=True)
    sort_blue = sorted(blue, key=itemgetter(0))

    cnt = 0
    for b in sort_blue:
        for r in sort_red:
            if r[0] < b[0] and r[1] < b[1]:
                cnt += 1
                sort_red.remove(r)
                break
    print(cnt)


main()

Submission status: Accepted

Solution code:
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

class MaxFlow:
    def __init__(self, node_count):
        self.node_count = node_count
        self.graph = [[] for _ in range(node_count)]

    def add_edge(self, u, v, cap):
        idx1 = len(self.graph[v])
        idx2 = len(self.graph[u])
        self.graph[u].append([v, cap, idx1])
        self.graph[v].append([u,   0, idx2])

    def dfs(self, u, t, f):
        if u == t:
            return f
        self.used[u] = True
        for i in range(len(self.graph[u])):
            v, cap, rev = self.graph[u][i]
            if self.used[v] == False and cap > 0:
                d = self.dfs(v, t, min(f, cap))
                if d:
                    self.graph[u][i][1] -= d
                    self.graph[v][rev][1] += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.used = [False] * self.node_count
            f = self.dfs(s, t, 1 << 29)
            if not f:
                return flow
            flow += f



n = getint()
a = [getints() for _ in range(n)]
b = [getints() for _ in range(n)]

src = n + n
dst = src + 1
nv = dst + 1
mf = MaxFlow(nv)

for i in range(n):
    mf.add_edge(src, i, 1)
    mf.add_edge(i + n, dst, 1)

for i in range(n):
    for j in range(n):
        if a[i][0] < b[j][0] and a[i][1] < b[j][1]:
            mf.add_edge(i, j + n, 1)

print (mf.max_flow(src, dst))

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)]
b.sort()
ans = 0
for i in range(n):
    Bx = b[i][0]
    By = b[i][1]
    tmp = []
    for j in range(len(r)):
        if r[j][0] <= Bx and r[j][1] <= By:
            dis = (Bx - r[j][0])**2 + (By - r[j][1])**2
            tmp.append([r[j][1],[r[j][0],r[j][1]]])
    if len(tmp) == 0:
        continue
    else:
        tmp.sort(reverse=True)
        ans += 1
        r.remove(tmp[0][1])
print(ans)

Submission status: Accepted

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

R = sorted(R, key = lambda x: -1*x[1])
B = sorted(B)

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:
n = int(input())
red = []
blue = []
for i in range(n):
    x,y =map(int,input().split())
    red.append([x,y])
for i in range(n):
    x,y =map(int,input().split())
    blue.append([x,y])

ans=0
for i in range(2*n):
    now = 2*n -1 -i
    for redpoint in red:
        if redpoint[0] == now:
            value=300
            add=[]
            for bid,bluepoint in enumerate(blue):
                if (bluepoint[0]>redpoint[0])and(bluepoint[1]>redpoint[1]):
                    if value>bluepoint[1]:
                        value =bluepoint[1]
                        add =bluepoint
            if add:
                blue.remove(add)
                red.remove(redpoint)
                ans +=1
            if redpoint[0]==redpoint[1] and add:
                break
        if redpoint[1] == now:
            value=300
            add=[]
            for bid,bluepoint in enumerate(blue):
                if (bluepoint[0]>redpoint[0])and(bluepoint[1]>redpoint[1]):
                    if value>bluepoint[0]:
                        value =bluepoint[0]
                        add =bluepoint
            if add:
                blue.remove(add)
                red.remove(redpoint)
                ans +=1
                        
print(ans)

Submission status: Accepted

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

a.sort()
b.sort()
res = 0
used = [False for i in range(n)]
for i in range(n):
  ind = -1
  cur = b[i]
  best = -1
  for j in range(n):
    if not used[j] and a[j][0] < cur[0] and a[j][1] < cur[1] and best < a[j][1]:
      ind = j
      best = max(best, a[j][1])
  if ind != -1:
    res+=1
    used[ind] = True

print(res)

Submission status: Accepted

Solution code:
#解説解答
n = int(input())
a = []
b = []
for i in range(n):
  a.append(list(map(int,input().split())) + [i])
for i in range(n):
  b.append(list(map(int,input().split())) + [i])
b.sort()
ans = 0
for bi in range(n):
  bnow = b[bi]
  acan = []
  for ai in range(n):
    anow = a[ai]
    if anow[0] < bnow[0] and anow[1] < bnow[1]:
      acan.append(anow)
  try:
    ause = max(acan, key = lambda x: x[1])
    a[ause[2]] = [1000,1000,'used']
    ans += 1
  except:
    pass
print(ans)

Submission status: Accepted

Solution code:
# ABC091C - 2D Plane 2N Points (ARC092C)
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = sorted(
        [tuple(map(int, input().split())) for _ in range(N)],
        key=lambda x: x[1],
        reverse=1,
    )
    B = sorted([tuple(map(int, input().split())) for _ in range(N)])
    ans, memo = 0, set()
    for bx, by in B:
        for i, (ax, ay) in enumerate(A):
            if i not in memo and ax < bx and ay < by:
                ans += 1
                memo |= {i}
                break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
R = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[1],reverse = True)
B = sorted([list(map(int,input().split())) for i in range(N)])
count = 0
l = []
for i in range(N):
    Bx = B[i][0]
    By = B[i][1]
    for j in range(N):
        if Bx > R[j][0] and By > R[j][1] and R[j][0] not in l:
            count += 1
            l.append(R[j][0])
            break
print(count)

Submission status: Accepted

Solution code:
N = int(input())

red = [0] * N
blue = [0] * N

for _ in range(N):
    red[_] = list(map(int, input().split()))

for _ in range(N):
    blue[_] = list(map(int, input().split()))

red = sorted(red, key=lambda x: (x[0], x[1]))
blue = sorted(blue, key=lambda x: (x[0], -x[1]), reverse=False)

ans = 0
# print("red:", red)
# print("blue:", blue)

for bp in blue:
    # print("check bp:", bp)
    rem = None
    
    if len(red) > 0:
        cand = None
        for rp in red:
            if bp[0] > rp[0] and bp[1] > rp[1]:
                if cand is None:
                    cand = rp
                else:
                    if cand[1] < rp[1]:
                        cand = rp

        # gen pair
        ans += 1 if cand is not None else 0
        rem = cand
        # print("pair with:", cand)

    if rem is not None:
        red.remove(rem)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

red = []
blue = []


for i in range(n):
    l = list(map(int,input().split()))
    red.append(l)
for i in range(n):
    l = list(map(int,input().split()))
    blue.append(l)

done = []

blue.sort()
for i in range(n):
    bag = []
    cnt = 0
    x = blue[i][0]
    y = blue[i][1]
    for j in range(n):
        if (x > red[j][0]) and (y > red[j][1]):
            if red[j] not in done:
                bag.append(red[j])
                cnt += 1
    bag.sort(key = lambda x:x[1])
    if cnt != 0:
        done.append(bag[cnt-1])

print(len(done))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    R = list(reversed(sorted(zip(a, b), key=lambda x: x[1])))
    B = sorted(zip(c, d), key=lambda x: x[0])
    P = [0] * N
    counter = 0
    for b in B:
        for i, (a, p) in enumerate(zip(R, P)):
            if p == 0 and a[0] < b[0] and a[1] < b[1]:
                P[i] = 1
                counter += 1
                break
    print(counter)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())  
red_li = [list(map(int, input().split())) for _ in range(n)]
blue_li = [list(map(int, input().split())) for _ in range(n)]
ans = 0
red_li.sort(reverse = True, key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[0], x[1]))

def count(red, blue):
    used_red = []
    used_blue = []
    for i in red:
        if i in used_red:
            continue
        for j in blue:
            if j in used_blue:
                continue
            if i[0] < j[0] and i[1] < j[1]:
                used_red.append(i)
                used_blue.append(j)
                break
    return len(used_red)


red_li.sort(reverse = True,key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())  
red_li = [list(map(int, input().split())) for _ in range(n)]
blue_li = [list(map(int, input().split())) for _ in range(n)]
ans = 0
red_li.sort(reverse = True, key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[0], x[1]))

def count(red, blue):
    used_red = []
    used_blue = []
    for i in red:
        if i in used_red:
            continue
        for j in blue:
            if j in used_blue:
                continue
            if i[0] < j[0] and i[1] < j[1]:
                used_red.append(i)
                used_blue.append(j)
                break
    return len(used_red)

ans = count(red_li, blue_li)
red_li.sort(reverse = True,key = lambda x : (x[1], x[0]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
red_li.sort(reverse = True,key = lambda x : (x[1], x[0]))
blue_li.sort( key = lambda x : (x[0], x[1]))
ans = max(ans, count(red_li, blue_li))
red_li.sort(reverse = True,key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [list(map(int,input().split())) for i in range(2*N)]

Alist = []
Blist = []

for i in range(N):
	Alist.append(X[i]+[0])
	Blist.append(X[i+N])

Alist.sort(key=lambda Alist:[-Alist[1],Alist[0]])
Blist.sort(key=lambda Blist:[Blist[0],-Blist[1]])
ans = 0
j = 0
while j<N:
	i = 0
	while i < len(Alist):
		if (Alist[i][0]<Blist[j][0] and Alist[i][1]<Blist[j][1]):
			ans += 1
			del Alist[i]
			break
		i+=1
	j+=1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[-x[1],x[0]])
b=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])
c=0
i=j=0
while j<n:
    i=0
    while i<len(a):
        if a[i][0]<b[j][0] and a[i][1]<b[j][1]:
            c+=1
            del a[i]
            break
        i+=1
    j+=1
print(c)

Submission status: Accepted

Solution code:
import collections


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  # TODO: must be Verified
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u]) - 1])
            self.edges[v].append([u, c, len(self.edges[u])])
            self.edges[u].append([v, 0, len(self.edges[v]) - 1])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = collections.deque([s])
        while que:
            v = que.popleft()
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(N)]
graph = Dinic(2*N+2)
for i in range(1, N+1):
    graph.add(0, i, 1)

for i in range(N+1, 2*N+1):
    graph.add(i, 2*N+1, 1)

for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph.add(i+1, N+1+j, 1)

print(graph.maxFlow(0, 2*N+1))

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
G = defaultdict(list)
rec = []
for i in range(n):
    a, b = map(int, input().split())
    rec.append((i, a, b))

for i in range(n):
    c, d = map(int, input().split())
    for index, p, q in rec:
        if p < c and q < d:
            G[index].append(i + n)
            G[i + n].append(index)

used = [False] * 2 * n
match = [-1] * 2 * n

def dfs(v):
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
# dfs(0)
# print(match)
# print((used))
ma = 0
for i in range(n):
    if match[i] < 0:
        used = [False] * 2 * n
        if dfs(i):
            ma += 1

print(ma)

Submission status: Accepted

Solution code:
from functools import reduce
import math
from operator import itemgetter

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    ab = []
    cd = []
    for i in range(N):
        s1, s2 = (int(_) for _ in input().split())
        ab.append((s1,s2))
    for i in range(N):
        s1, s2 = (int(_) for _ in input().split())
        cd.append((s1,s2))
    cnt = 0
    ab = sorted(ab, key = itemgetter(0))
    cd = sorted(cd, key = itemgetter(0))
    for i in range(N):
        rp = -1
        tmp = -1
        for j in range(len(ab)):
            # print(ab[j],cd[i])
            if ab[j][0]<cd[i][0] and ab[j][1]<cd[i][1]:
                if ab[j][1] > tmp:                    
                    tmp = ab[j][1]
                    rp = j
        if rp >=0:
            # print(ab[rp])
            ab.pop(rp)
            cnt +=1
    print(cnt)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
CD = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)
CD.sort()
ans = 0

for i, red in enumerate(AB):
    for j, blue in enumerate(CD):
        if red[0] < blue[0] and red[1] < blue[1]:
            ans += 1
            CD.pop(j)
            break
print(ans)

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)]
v=[]
r.sort()
b.sort()
count=0
 
for i in range(n):
    for j in range(len(r)):
        if b[i][0]<=r[j][0] or b[i][1]<=r[j][1]:
            pass
        else:
            v.append(r[j])    
    if v!=[]:
        v.sort(key=lambda x:x[1])
        v.reverse()
        r.remove(v[0])
        
            
        v=[]
        count+=1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted((tuple(map(int,input().split())) for _ in [0]*N),key=lambda x:(x[0],-x[1]))
CD = sorted((tuple(map(int,input().split())) for _ in [0]*N),key=lambda x:(x[0],-x[1]))
ans = 0
for c,d in CD:
    m = max([b for a,b in AB if a<c and b<d]+[-1])
    if m==-1:continue
    for i,ab in enumerate(AB):
        a,b = ab
        if b == m:
            ans += 1
            AB[i] = (1000,1000)
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

R = [(0, 0)] * N
for n in range(N):
  x, y = map(int, input().split())
  R[n] = (x, y)

B = [[0, 0]] * N
for n in range(N):
  x, y = map(int, input().split())
  B[n] = (x, y)

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

ans = 0

for (bx, by) in B:
  max_y = -1
  idx = 0
  for i, (rx, ry) in enumerate(R):
    if rx < bx and max_y < ry < by:
      max_y = ry
      idx = i
  if max_y > -1:
    ans += 1
    R.pop(idx)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    N = int(input())
    aka = []
    ao = []
    for i in range(N):
        a,b = map(int, input().split())
        aka.append((a,b,False))
            
    for i in range(N):
        c,d = map(int, input().split())
        ao.append((c,d))
            
    ao.sort()
    ans = 0
    for i, val in enumerate(ao):
        c, d = val
        y_max = -1
        index = -1
        for j , vol in enumerate(aka):
            a, b, partner = vol
            if a < c and b < d and partner == False:
                if y_max == -1 or y_max < b:
                    y_max = b
                    index = j
                    
        if y_max != -1:
            ans += 1
            a, b, partner = aka[index]
            partner = True
            aka[index] = (a, b, partner)
            y_max = -1
            index = -1
            
    print(ans)
    
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
r = []
b = []

for i in range(n):
    x,y = map(int,input().split())
    r.append([x,y])

for i in range(n):
    x,y = map(int,input().split())
    b.append([x,y])



r.sort(key=lambda x:[x[0],x[1]])
b.sort(key=lambda x:[x[1],x[0]])


ans = 0
for i in range(n):
    x,y = b[i][0],b[i][1]
    tar = 0
    flag = False
    # print(r)
    # print(b)
    for j in range(len(r)):
        if r[j][0] < x and r[j][1] < y:
            flag = True
            tar = j
    if flag:
        ans += 1
        r.pop(tar)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC91 C

from operator import itemgetter
n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
red = sorted(red,key = itemgetter(1),reverse = True)
blue = sorted(blue,key = itemgetter(0))
checkr = [True]*n
checkb = [True]*n

pair = 0
for c,d in blue:
    for j in range(n):
        a,b = red[j]
        if a < c and b < d and checkr[j]:
            pair += 1
            checkr[j] = False
            break
print(pair)