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 = []
c = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    a.append([x1,y1])
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    c.append([x1,y1])
a = sorted(a,key=lambda x:-x[1])
c = sorted(c,key=lambda x:x[0])
ans = 0
for i in range(n):
  e = c[i]
  for j in range(len(a)):
    if (e[0] > a[j][0] and e[1] > a[j][1]):
      a.pop(j)
      ans += 1
      break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
rn = [[True]+list(map(int,input().split())) for _ in range(N)]
bn = sorted([list(map(int,input().split())) for _ in range(N)])
rn.sort(key=lambda x: -x[2])
for bp in bn:
  bx,by = bp
  for rp in rn:
    f,rx,ry = rp
    if f and rx<bx and ry<by:
      rp[0] = False
      break
print(sum([0 if rp[0] else 1 for rp in rn]))

Submission status: Accepted

Solution code:
n = int(input())

red = []

for i in range(n):
	red.append(map(int,raw_input().split()))

blue = []

for i in range(n):
	blue.append(map(int,raw_input().split()))


redflug = []
for i in range(n):
	redflug.append(0)

blue.sort()

ans = 0
for i in range(n):
	t = -1
	maxy = -1
	for j in range(n):
		if redflug[j] == 0 and blue[i][0] > red[j][0] and blue[i][1] > red[j][1] and red[j][1] > maxy :
			t = j
			maxy = red[j][1]

	if t != -1 :
		redflug[t] = 1
		ans += 1

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)]
R.sort(key = lambda x:x[1], reverse=True)
B.sort(key = lambda x:x[0], reverse=False)
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 = [tuple(int(x) for x in input().split()) for _ in range(n)]
blue = [tuple(int(x) for x in input().split()) for _ in range(n)]

red = sorted(red)
blue = sorted(blue)

ans = 0
for x, y in blue:
    if x == 0:
        continue
    else:
        temp = [-1, -1]
        for a, b in red:
            if a > x:
                break
            elif y > b > temp[1]:
                temp = [a, b]
        if temp[1] >= 0:
            ans += 1
            red.remove((temp[0], temp[1]))

print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**7)
N=int(input())
#0がスタート,1-Nがあか、N+1-2Nが青,2N+1がゴール
table=[[0]*(2*N+2) for i in range(2*N+2)]
for i in range(1,N+1):
    table[0][i]=1
    table[i+N][2*N+1]=1    
red=[]
blue=[]
for i in range(1,N+1):
    a,b=map(int,input().split())
    red.append((i,a,b))
for i in range(1,N+1):
    a,b=map(int,input().split())
    blue.append((i,a,b))
for i,a,b in red:
    for j,x,y in blue:
        if a<x and b<y:
            table[i][N+j]=1
def fk(x):
    visit[x]=True
    if x==2*N+1:
        return True
    for i in range(2*N+2):
        if (not visit[i]) and table[x][i]>0:
            if fk(i):
                table[x][i]-=1
                table[i][x]+=1
                return True
    return False

ans=0
while True:
    visit=[False]*(2*N+2)
    if fk(0):
        ans+=1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(i) for i in reversed(input().split())] for n in range(N)]
B = [[int(i) for i in input().split()] for n in range(N)]
A.sort(); A.reverse(); B.sort()
C = 0
i = 0
for b in B:
  found = False
  while not found:
    a = A[i]
    if a[1] < b[0] and a[0] < b[1]:
      found = True
      C += 1
      A.pop(i)
      i = 0
    elif i+1 == len(A):
      found = True
      i = 0
    else:
      i += 1
print(C)

Submission status: Accepted

Solution code:
N=int(input())
red=[list(map(int, input().split())) for _ in range(N)]
blue=[list(map(int, input().split())) for _ in range(N)]
red.sort(key=lambda x:x[1])
blue.sort(key=lambda x:x[0])
ct=0
for i in blue:
    for j in reversed(red):
        if i[0]>j[0] and i[1]>j[1]:
            red.remove(j)

            ct+=1
            break
print(ct)

Submission status: Accepted

Solution code:
from collections import deque

#Dinic法 from https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow
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'))

#入力
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):
  a,b=map(int,input().split())
  blue.append([a,b])

#N個とN個のマッチング。source/sinkを加えた2+2*Nの最大流に帰着させる
#各点からsource/sinkにパスを張る
mf=Dinic(2*N+2)
for i in range(1,N+1):
  mf.add_link(0, i, 1)
for i in range(N+1,2*N+1):
  mf.add_link(i, 2*N+1, 1)

#マッチング条件を満たす２点にパスを張る
for i in range(N):
  for j in range(N):
    a,b=red[i]
    c,d=blue[j]
    if a<c and b<d:
      mf.add_link(i+1, N+1+j, 1)
      
print(mf.max_flow(0, 2*N+1))

Submission status: Accepted

Solution code:
N=input()
A=[ map(int, raw_input().split())  for i in range(N) ]
C=[ map(int, raw_input().split())  for i in range(N) ]

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

V=[0 for i in range(N+1)]

ans=0

for bx,by in C:
	for i,u  in enumerate(A):
		rx=u[0]
		ry=u[1]
		if bx>rx and by>ry and V[i]==0:
			ans+=1
			V[i]=1
			break

print ans

Submission status: Accepted

Solution code:
n = int(input())
a = []
c = []

for i in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    c.append([int(i) for i in input().split()])

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

count = 0
for i, (tc, td) in enumerate(c):
    for j, (ta, tb) in enumerate(a):
        if ta < tc and tb < td:
            count += 1
            a.pop(j)
            break

print(count)

Submission status: Accepted

Solution code:
N = int(input())
ab = []
cd = []
for i in range(N):
    ab.append(list(map(int, input().split())))
for i in range(N):
    cd.append(list(map(int, input().split())))
    
ab.sort(key=lambda x:x[0],reverse=True)
cd.sort(key=lambda x:x[1])


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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(2*N)]
es = [[] for i in range(2*N)]
for i,(x1,y1) in enumerate(src[:N]):
    for j,(x2,y2) in enumerate(src[N:]):
        if x1 < x2 and y1 < y2:
            es[i].append(j+N)
            es[j+N].append(i)

used = [False] * (2*N)
match = [-1] * (2*N)

def _dfs(v):
    global used, match
    used[v] = True
    for u in es[v]:
        w = match[u]
        if w < 0 or not used[w] and _dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

def bipartite_matching():
    global used, match
    ret = 0
    for v in range(2*N):
        if match[v] < 0:
            used = [False] * (2*N)
            if _dfs(v):
                ret += 1
    return ret

print(bipartite_matching())

Submission status: Accepted

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

for c, d in list_blue:
    for a ,b in list_red:
        if a < c and b < d:
            list_red.remove([a, b])
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red_points  = sorted([list(map(int, input().split())) for i in range(N)], key = lambda x: (-x[1], -x[0]))
blue_points = sorted([list(map(int, input().split())) for i in range(N)], key = lambda x: (x[0], x[1]))
for blue_point in blue_points:
    blue_point.append(False)

ans = 0
for red_point in red_points:
    for blue_point in blue_points:
        if red_point[0] < blue_point[0] and red_point[1] < blue_point[1] and not blue_point[2]:
            ans += 1
            blue_point[2] = True
            break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
red_coodinates=[]
blue_coodinates=[]
for i in range(N):
    red_coodinates.append(list(map(int,input().split())))
for i in range(N):
    blue_coodinates.append(list(map(int,input().split())))

red_coodinates.sort(key=lambda x:-x[1])
blue_coodinates.sort()
number_of_pairs=0

for i in range(N):
    for j in range(0,len(red_coodinates)):
        if red_coodinates[j][0]<blue_coodinates[i][0] and red_coodinates[j][1]<blue_coodinates[i][1]:
            number_of_pairs+=1
            red_coodinates.remove(red_coodinates[j])
            break
        else:
            pass

print(number_of_pairs)

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)]
a = [0] * N
for x,y in sorted(blue,key=lambda x: x[0]):
    k = []
    for i,[x2,y2] in enumerate(red):
        if x2 < x and y2 < y and not a[i]:
            k.append((x2,y2,i))
    if len(k):
        x,y,i=sorted(k,key=lambda x:-1*x[1])[0]
        a[i] = 1
print(sum(a))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = 0

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# your code goes here
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
ans = 0
red = sorted(red, key = lambda x:  x[1]*(-1))
blue = sorted(blue)

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())
s, t = [], []
for i in range(n):
  a, b = list(map(int, input().split()))
  s.append((a, b))
for i in range(n):
  c, d = list(map(int, input().split()))
  t.append((c, d))
s.sort(key=lambda x:x[1])
t.sort()

ans = 0
for i in range(n):
  for j in range(n-1, -1, -1):
    if s[j]==None:
      continue
    if s[j][0]<t[i][0] and s[j][1]<t[i][1]:
      ans+=1
      s[j] = None
      break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
import bisect
w=0
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))
b.sort()
r.sort()   
for i,j in b:
    u=[]
    for k in range(len(r)):
        if i>r[k][0] and j>r[k][1]:
            u.append((r[k][1],r[k][0]))
    if u:        
        u.sort()   
        (p,q)=u[-1]
        r.remove((q,p))
        w+=1
print(w)

Submission status: Accepted

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

# 青い点を探して処理する関数
def search_bluedot(end_x, end_y):
	# 更新する値をグローバル宣言
	global ans
	global field
	# Y軸向きには値の大きい方から優先して取るために、逆順でループ回す
	for y in range(end_y-1, -1, -1):
		for x in range(end_x):
			# 赤い点を見つけたら、答えを+1して赤い点を消す
			if field[y][x] == 1:
				ans += 1
				field[y][x] = 0
				return

dot_count = int(input())
# 点を置くフィールドを作成
field = [[0 for i in range(dot_count*2)] for j in range(dot_count*2)]
# 赤い点の配置
for i in range(dot_count):
	x, y = map(int, input().split())
	field[y][x] = 1
# 青い点の配置
for i in range(dot_count):
	x, y = map(int, input().split())
	field[y][x] = 2

ans = 0
for x in range(dot_count*2):
	# X軸向きに最も値の小さいものから取るために、Y軸ループを内側にする
	for y in range(dot_count*2):
		# 青い点を見つけたら、そこより内側で赤い点を探す
		if field[y][x] == 2:
			search_bluedot(x, y)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

ab=[]
cd=[]

for i in range(N):
    e,f=map(int,input().split())
    tmp=[e,e,f]
    ab.append(tmp)

for i in range(N):
    e,f=map(int,input().split())
    tmp=[e,e,f]
    cd.append(tmp)

ab.sort()
cd.sort()

#ab.reverse()
#cd.reverse()

ans=0

for i in range(N):
    L=len(ab)
    mi=1000000
    num=-1
    for j in range(L):
        if ab[j][1]<cd[i][1] and ab[j][2]<cd[i][2]:
            tmp=abs(ab[j][2]-cd[i][2])
            if tmp<mi:
                mi=tmp
                num=j
    if not num<0:
        del ab[num]
        ans+=1


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
ans = 0
red = sorted(red, key = lambda x:x[1] * -1)
blue = sorted(blue)
for b in blue:
	for r in red:
		if b[0] > r[0] and b[1] > r[1]:
			ans += 1
			red.remove(r)
			break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
ans = 0
red = sorted(red, key = lambda x: -1 * x[1])
blue = sorted(blue)
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:
from operator import itemgetter
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=itemgetter(0),reverse=True)
ab.sort(key=itemgetter(1),reverse=True)
cd.sort(key=itemgetter(1))
cd.sort(key=itemgetter(0))
count = 0
for c,d in cd[:]:
    for a,b in ab:
        if a < c and b < d:
            count += 1
            ab.remove([a,b])
            cd.remove([c,d])
            break
print(count)

Submission status: Accepted

Solution code:
N=int(input())
r=[(0,0) for i in range(N)]
b=[(0,0) for i in range(N)]

for i in range(N):
    x,y=map(int,input().split())
    r[i]=(x,y)
for i in range(N):
    x,y=map(int,input().split())
    b[i]=(x,y)
b.sort()
ru=[0 for i in range(N)]
ans=0
for i in range(N):
    k=-1
    for j in range(N):
        if b[i][0]>r[j][0] and b[i][1]>r[j][1]:
            if k==-1 and ru[j]==0:
                k=j
            elif r[k][1]<r[j][1] and ru[j]==0:
                k=j
    if k!=-1:
        ru[k]=1
        ans+=1
print(ans)

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[1], x[0]), reverse=True)
blue.sort(key=lambda x: (x[0], x[1]))

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

Submission status: Accepted

Solution code:
N=int(input())
reds = set()
blues = []
for i in range(N):
    x,y=map(int,input().split())
    reds.add((x,y))
for i in range(N):
    x,y=map(int,input().split())
    blues.append((x,y))
blues.sort(key=lambda x: x[0])
ans = 0
for (bx,by) in blues:
    candidates = []
    for (rx,ry) in reds:
        if rx < bx and ry < by:
            candidates.append((rx,ry))
    if candidates:
        candidates.sort(key = lambda x: -x[1])
        ans += 1
        reds.remove(candidates[0])
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

blue_dict = defaultdict(list)
for c, d in blues:
    for a, b in reds:
        if a < c and b < d:
            blue_dict[c, d].append((a, b))
for val in blue_dict.values():
    val.sort(key=lambda x:-x[1])

red_dict = {}
for blue, red_list in sorted(blue_dict.items(), key=lambda x:x[0][0]):
    for red in red_list:
        if red in red_dict:
            continue
        red_dict[red] = blue
        break

print(len(red_dict))

Submission status: Accepted

Solution code:
N=int(input())

RED=[None]*N

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

BLUE=[None]*N

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


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

BLUE.sort(key=lambda x:x[1])

score=0
for i in range(N-1,-1,-1):
    for j in range(len(BLUE)):
        if RED[i][0]<BLUE[j][0] and RED[i][1]<BLUE[j][1]:
            score+=1
            del(BLUE[j])
            break

print(score)

Submission status: Accepted

Solution code:
import collections

class MaxFlow:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class Edge:
        def __init__(self, to, rev, cap):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, fr, to, cap):
        self.E[fr].append(self.Edge(to, len(self.E[to]), cap))
        self.E[to].append(self.Edge(fr, len(self.E[fr])-1, 0))

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)

N = int(input())
G = MaxFlow(300)

AB = []
for i in range(1,N+1):
	a,b = input().split()
	a_i = int(a)
	b_i = int(b)
	AB.append((a_i,b_i))

	G.add_edge(0,i,1)

CD = []
for j in range(N+1,2*N+1):
	c,d = input().split()
	c_i = int(c)
	d_i = int(d)
	CD.append((c_i,d_i))

	G.add_edge(j,2*N+1,1)


for n in range(1,N+1):
	for m in range(N+1,2*N+1):
		if((AB[n-1])[0]<(CD[m-(N+1)])[0] and (AB[n-1])[1]<(CD[m-(N+1)])[1]):
			G.add_edge(n,m,1)

flow_value = G.dinic(0,2*N+1)
print(int(flow_value))

Submission status: Accepted

Solution code:
import random
from operator import itemgetter

N = int(input())
AB = []
for i in range(0,N):
	a,b = input().split()
	a_i = int(a)
	b_i = int(b)
	AB.append((a_i,b_i))

CD = []
for j in range(0,N):
	c,d = input().split()
	c_i = int(c)
	d_i = int(d)
	CD.append((c_i,d_i))

CD.sort()
AB.sort()

count = 0
for n in range(0,N):
	list_AB = []
	for m in range(0,len(AB)):

		if((AB[m])[0]<(CD[n])[0]):
			list_AB.append(AB[m])
	
	if(list_AB != []):
		list_AB = sorted(list_AB, key=itemgetter(1))
		list_AB.reverse()

		for q in range(0,len(list_AB)):
			if((list_AB[q])[1]<(CD[n])[1]):
				count += 1
				AB.remove(list_AB[q])
				break

print(count)

Submission status: Accepted

Solution code:
n = int(input())
R = []
for v in range(n):
    b = tuple(map(int, input().split(' ')))
    R.append(b)
R.sort()
B = []
for v in range(n):
    r = tuple(map(int, input().split(' ')))
    B.append(r)
B.sort()
count = 0
i = 0
while i < n:
    j = 0
    Bmax = -1
    Bind = -1
    while j < len(R) and B[i][0] > R[j][0]:
        if R[j][1] < B[i][1] and Bmax < R[j][1]:
            Bmax = R[j][1]
            Bind = j
        j += 1
    if Bmax != -1:
        del R[Bind]
        count += 1
    i += 1
print(count)

Submission status: Accepted

Solution code:
# input
N = int(input())
lst_red = [list(map(int, input().split())) for i in range(N)]
lst_blue = [list(map(int, input().split())) for i in range(N)]

lst_red.sort(key=lambda x: x[1], reverse=True) # yの大きい順
lst_blue.sort(key=lambda y: y[0]) # xの小さい順

ans = 0

# 貪欲法
# 各青点に対してペアになれる赤点のうち、yが最大の赤点を選んでいく
for b in lst_blue:
    for r in lst_red:
        if r[0] < b[0] and r[1] < b[1]:
            lst_red.remove(r)
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
def m():
    n = int(input())
    red = [list(map(int, input().split())) for _ in range(n)]
    blue = [list(map(int, input().split())) for _ in range(n)]
    red.sort(key=lambda x: x[1], reverse=True) # yの大きい順
    blue.sort(key=lambda y: y[0]) # xの小さい順
    ans = 0
    for b in blue:
        for r in red:
            if r[0] < b[0] and r[1] < b[1]:
                red.remove(r)
                ans +=1
                break
    return ans

print(m())

Submission status: Accepted

Solution code:
class point:
    def __init__(self,x,y):
        self.x = x
        self.y = y

if __name__ == '__main__':
    N = int(raw_input())
    red = []
    blue = []
    for i in range(N):
        x,y = map(int, raw_input().split())
        red.append(point(x,y))

    for i in range(N):
        x,y = map(int, raw_input().split())
        blue.append(point(x,y))


    blue = sorted(blue, key=lambda k: k.x)
    red = sorted(red, key=lambda k: k.y, reverse=True)
    red_check = [0] * N
    ans = 0
    for b in blue:
        red_pair = None
        is_check = True
        for i, r in enumerate(red):
            if b.x > r.x and b.y > r.y and is_check and red_check[i] == 0:
                red_pair = r
                is_check = False
                red_check[i] = 1

        if red_pair is not None:
            ans += 1

    print(ans)

Submission status: Accepted

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

ans = 0
for c, d in sorted(blue, key=lambda x: x[0]):
    for a, b in sorted(red, key=lambda x: x[1], reverse=True):
        if a < c and b < d:
            ans += 1
            red.remove([a, b])
            break
print(ans)

Submission status: Accepted

Solution code:
def main():
    PointNum = int(input())
    
    rPoint = []
    bPoint = []
    for i in range(PointNum):
        rPoint.append([int(i) for i in input().split()] )
    for i in range(PointNum):
        bPoint.append([int(i) for i in input().split()] )
        
#    print(rPoint)
#    print(bPoint)
    sorted_rPoint = sorted(rPoint)
    sorted_bPoint = sorted(bPoint)
#    print(sorted_rPoint)
#    print(sorted_bPoint)
    
    count = 0
    for bp in sorted_bPoint:
        ans_p = [-1, -1]
        IsAnsFind = False
        for rp in sorted_rPoint:
            if(bp[0]>rp[0] and bp[1]>rp[1]):
#                print(bp)
#                print(rp)
                IsAnsFind = True
                if(rp[1] > ans_p[1]):
                    ans_p = rp[:]
        if(IsAnsFind):
            count += 1
            sorted_rPoint.remove(ans_p)
    
    print(count)
    
if __name__=="__main__":
    main()

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])
count = 0
for i in range(N):  # B
    for j in range(N):  # R
        if R[j][0] < B[i][0] and R[j][1] < B[i][1]:
            count += 1
            R[j][0] = 1000000
            R[j][1] = 1000000
            B[i][0] = -1
            B[i][1] = -1
            break
print(count)

Submission status: Accepted

Solution code:
n=int(input())
b=[[int(i) for i in input().split()] for j in range(n)]
a=[[int(i) for i in input().split()] for j in range(n)]
a=sorted(a,key=lambda x:x[0])
b=sorted(b,key=lambda x:x[1],reverse=True)
ans=0

for ai in range(n):
  for bi in range(len(b)):
    if b[bi][0]<a[ai][0] and b[bi][1]<a[ai][1]:
      ans+=1
      del b[bi]
      break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red_point=[]
blue_point=[]
for i in range(N):
    red_point.append(list(map(int,input().split())))
for i in range(N):
    blue_point.append(list(map(int,input().split())))
red_point.sort(reverse=True)
blue_point.sort(key=lambda x:x[1])
# print(blue_point)
ans = 0
# temp = 0 
# print(red_point)
for i in range(N):
    redx,redy=red_point[i][0],red_point[i][1]
    for j in range(len(blue_point)):
        # print("({},{})".format(i,j))
        # print(blue_point)
        bluex,bluey=blue_point[j][0],blue_point[j][1]
        if redx<bluex and redy<bluey:
            # if temp<redx:
                # temp = redx
                # tempj=j   
            ans +=1
            # red_point.pop(i)
            blue_point.pop(j)
            break
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:
from operator import itemgetter
N = int(input())
A = []
B = []
for i in range(N):
    u, v = map(int, input().split())
    A.append((u, v))
for i in range(N):
    u, v = map(int, input().split())
    B.append((u, v))
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:
N=int(input())
graphs = [['' for x in range(2*N)] for x in range(2*N)]
for i in range(N):
  x,y=map(int,input().split())
  graphs[x][y] = 'r'
for j in range(N):
  x,y=map(int,input().split())
  graphs[x][y] = 'b'
rqueue = []
count = 0
for k in range(2*N):
  for l in range(2*N):
    if graphs[k][l] == 'r':
      rqueue.append(tuple([k,l]))
      rqueue.sort(key=lambda x:x[1],reverse=True)
    elif graphs[k][l] == 'b':
      for m in range(len(rqueue)):
        if rqueue[m][0] < k and rqueue[m][1] < l:
          rqueue.pop(m)
          count += 1
          break
print(count)

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 = list(reversed(sorted(red, key=lambda x: x[1])))
blue = sorted(blue)
ans = 0
done = []
for pos in blue:
  i = 0
  while i < n:
    if pos[0] > red[i][0] and pos[1] > red[i][1] and not i in done:
      done.append(i)
      ans += 1
      i += 1
      break
    i += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
cd = [list(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda xy:xy[1], reverse=True)
cd.sort()
ans = 0
for b in cd:
    for r in ab:
        if(r[0] < b[0] and r[1] < b[1]):
            ab.remove(r)
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red = []
blue = []
used_r = [False for _ in range(n)]
used_b = [False for _ in range(n)]
for i in range(n):
    tmp, tmp2 =  map(int, input().split())
    red.append((tmp,tmp2))
for i in range(n):
    tmp, tmp2 =  map(int, input().split())
    blue.append((tmp,tmp2))
red = sorted(red, key=lambda x: -1*x[1])
blue = sorted(blue)
cnt = 0
for j in range(n):
    for i in range(n):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            if used_r[i] or used_b[j]:
                continue
            else:
                cnt += 1
                used_r[i] = True
                used_b[j] = True
                break
print(cnt)