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())
reds = sorted([tuple(map(int, input().split())) for _ in range(N)], reverse=True, key=lambda x: x[1])
blues = sorted([tuple(map(int, input().split())) for _ in range(N)])
# print(reds)
# print(blues)
ans = 0
for b in blues:
    for r in reds:
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            reds.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)]

reds.sort(key=lambda x: x[0], reverse=True)
blues.sort(key=lambda x: x[0])

res = 0
for r in reds:
    b_list = [b for b in blues if r[0] < b[0] and r[1] < b[1]]

    if len(b_list):
        b = min(b_list, key=lambda x: x[1])
        blues.remove(b)
        res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, product
n = int(input())
red_ls = []
blue_ls = []
for j in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    red_ls.append([1+j, a, b])
for j in range(n):
    c, d = [int(i) for i in sys.stdin.readline().split()]
    blue_ls.append([n+1+j, c, d])

graph = {i : [] for i in range(2*n+2)}
edge_ls = []
cnt = 0
for i in range(1, n+1):
    edge_ls.append([i, 1, None])
    graph[0].append(cnt)
    cnt += 1
for i in range(n+1, 2*n+1):
    edge_ls.append([2*n+1, 1, None])
    graph[i].append(cnt)
    cnt += 1

for (r_ind, r_x, r_y), (b_ind, b_x, b_y) in product(red_ls, blue_ls):
    if r_x < b_x and r_y < b_y:
        edge = [b_ind, 1, cnt+1]
        edge_rev = [r_ind, 0, cnt]
        graph[r_ind].append(cnt)
        graph[b_ind].append(cnt + 1)
        edge_ls += [edge, edge_rev]
        cnt += 2

def dfs(s, g, flow):
    if s==g:
        return flow
    used[s] = True
    for _next in graph[s]:
        t, c, rev = e = edge_ls[_next]
        if not used[t] and c > 0:
            flow = min(flow, c)
            d = dfs(t, g, flow)
            if d:
                edge_ls[_next][1] -= d
                if rev is not None:
                    edge_ls[rev][1] += d
                return d
    return 0


flow = 0
INF = 10**18
f = INF
while f:
    used = [0 for i in range(2*n+2)]
    f = dfs(0, 2*n+1, INF)
    flow += f
print(flow)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    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(lambda x:x[1],reverse=1)
    CD.sort()

    ans=0
    for i in range(n):
        c,d=CD[i]
        for j in range(n):
            a,b=AB[j]
            if(a<c and b<d):
                AB[j]=[INF,INF]
                CD[i]=[-INF,-INF]
                ans+=1
                break
    print(ans)
resolve()

Submission status: Accepted

Solution code:



N = int(input())

r = []
for _ in range(N):
    x,y = map(int, input().split())
    r.append((-y,x))

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

r.sort()
b.sort()

ans = 0
for my,x in r:
    for j in range(len(b)):
        if  -my < b[j][1] and x < b[j][0]:
            ans += 1
            b.pop(j)
            break

print(ans)

Submission status: Accepted

Solution code:
# ABC091C
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()
ans = 0

for i in range(N):
    blue_x , blue_y = cd[i][0], cd[i][1]
    red_list_x = []
    red_list_y = []
    red_list_index = []
    for k in range(len(ab)):
        red_x, red_y = ab[k][0], ab[k][1]
        if blue_x > red_x and blue_y > red_y:
            red_list_x.append(red_x)
            red_list_y.append(red_y)
            red_list_index.append(k)
    if red_list_index:
        loc = red_list_index[red_list_y.index(max(red_list_y))]
        ans += 1
        del ab[loc]
        

print(ans)

Submission status: Accepted

Solution code:
import sys
if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

N = int(input())
A = [[False,MAP()] for _ in range(N)]
B = [[False,MAP()] for _ in range(N)]

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

#after reading answer
count = 0
for b in B:
	cand = []
	for a in A:
		if b[0] or a[0] : continue
		#print(b[1],a[1])
		if b[1][0] > a[1][0] and b[1][1] > a[1][1]:
			#print('make pair')
			b[0] = True
			a[0] = True
			count += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
b=[]
for i in range(n):
    b.append(list(map(int,input().split())))
b.sort()
a=sorted(a,key=lambda x: -x[1])
ans=0
vb=[]
for i in range(n):
    for j in range(n):
        if not j in vb:
            if a[i][0]<b[j][0] and a[i][1]<b[j][1]:
                vb.append(j)
                ans+=1
                break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lst1 = []
lst2 = []
for i in range(N):
    lst1.append(list(map(int, input().split())))
for i in range(N):
    lst2.append(list(map(int, input().split())))
lst1.sort()
lst2.sort()
cnt = 0
for i in lst2:
    ans = []
    for j in lst1:
        if i[0] <= j[0]:
            break
        else:
            if i[1] > j[1]:
                ans.append(j[::-1])
    if not ans:
        continue
    else:
        lst1.remove(max(ans)[::-1])
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
b = []
r = []
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 = sorted(r)
b = sorted(b)

b_f = [-1] * n
r_f = [-1] * n

pair = []
count = 0
for i in range(n):
    if b_f[i] == -1:
        tmp = []
        for j in range(n):
            if b[i][0] > r[j][0] and b[i][1] > r[j][1] and r_f[j] == -1:
                tmp.append(j)
            
        if len(tmp) != 0:     
            pair_j = max(tmp, key=lambda j: r[j][1])
            count += 1
            b_f[i] = 1
            r_f[pair_j] = 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())

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

CD = []    
for i in range(N):
    tmp = list(map(int, input().split()))
    CD.append(tmp)
    
AB = sorted(AB, key=lambda x: x[1], reverse=True)
CD = sorted(CD)

ans = 0
for cd in CD:
    for ab in AB:
        if cd[0] > ab[0] and cd[1] > ab[1]:
            ans += 1
            AB.remove(ab)
            break
        
print(ans)

Submission status: Accepted

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

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

abl = sorted(abl)

# Hopcroft-Karp Algorithm
from collections import deque
class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        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)
        self.level = level
        return level[1] is not None

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

    def flow(self):
        flow = 0
        G = self.G
        bfs = self.bfs; dfs = self.dfs
        while bfs():
            *self.it, = map(iter, G)
            while dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

karp = HopcroftKarp(n,n)

for i in range(n):
    for j in range(n):
        if abl[i][0] < cdl[j][0] and abl[i][1] < cdl[j][1]:
            karp.add_edge(i,j)
            
print(karp.flow())

Submission status: Accepted

Solution code:
#最大二部マッチング
def dfs(v, edges, n, visited, matched):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], edges, n, visited, matched):
            matched[u] = v
            return True
    return False
def examC():
    N = I()
    ab = [LI() for _ in range(N)]
    cd = [LI() for _ in range(N)]
    xn = N; yn = N
    matched = [-1] * yn
    E = [set() for _ in range(xn)]
    for i in range(xn):
        for j in range(yn):
            if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
                E[i].add(j)
    ans = 0
    for s in range(xn):
        ans += dfs(s, E, yn, set(), matched)
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
N = int(input())
red = [[int(x) for x in input().split()] for _ in range(N)]
blue = [[int(x) for x in input().split()] for _ in range(N)]

red.sort(reverse=True)
blue.sort(key=lambda x: x[1])
pairedBlue = [False] * N

ans = 0
for r in red:
    for id, b in enumerate(blue):
        if pairedBlue[id]:
            continue
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            pairedBlue[id] = True
            break

print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())

red = []
for i in range(N):
    x,y = map(int, input().split())
    heapq.heappush(red, (-y, x))

blue = []
for i in range(N):
    x,y = map(int, input().split())
    heapq.heappush(blue, (x,y))

ans = 0
for i in range(N):
    tmp = []
    bx,by = heapq.heappop(blue)
    flag = True
    while flag:
        mry, rx = heapq.heappop(red)
        if bx > rx and by > -mry:
            ans += 1
            flag = False
            if len(tmp) > 0:
                for mry,rx in tmp:
                    heapq.heappush(red, (mry, rx))
        else:
            tmp.append((mry, rx))

        if len(red) == 0:
            if len(tmp) > 0:
                for mry,rx in tmp:
                    heapq.heappush(red, (mry, rx))
            break
            
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        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)
        self.level = level
        return level[1] is not None

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

    def flow(self):
        flow = 0
        G = self.G
        bfs = self.bfs; dfs = self.dfs
        while bfs():
            *self.it, = map(iter, G)
            while dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

def resolve():
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    CD=[tuple(map(int,input().split())) for _ in range(n)]

    mm=HopcroftKarp(n,n)
    for i in range(n):
        a,b=AB[i]
        for j in range(n):
            c,d=CD[j]
            if(a<c and b<d):
                mm.add_edge(i,j)
    print(mm.flow())
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
class Dinic(object):
    def __init__(self,n):
        self.__n=n
        self.__E=[[] for _ in range(n)]
        self.__level=None
        self.__iter=None

    def add_link(self,u,v,w):
        self.__E[u].append([v,w,len(self.__E[v])])
        self.__E[v].append([u,0,len(self.__E[u])-1])

    def __bfs(self,s):
        level=[-1]*self.__n
        level[s]=0
        Q=deque([s])
        while(Q):
            v=Q.popleft()
            for nv,w,rev in self.__E[v]:
                if(w>0 and level[nv]<0):
                    level[nv]=level[v]+1
                    Q.append(nv)
        self.__level=level

    def __dfs(self,v,t,flow):
        if(v==t): return flow
        for i in range(self.__iter[v],len(self.__E[v])):
            self.__iter[v]=i
            nv,w,rev=self.__E[v][i]
            if(w==0 or self.__level[v]>=self.__level[nv]): continue
            d=self.__dfs(nv,t,min(flow,w))
            if(d==0): continue
            self.__E[v][i][1]-=d
            self.__E[nv][rev][1]+=d
            return d
        return 0

    def flow(self,s,t):
        flow=0
        while(True):
            self.__bfs(s)
            if(self.__level[t]<0): return flow
            self.__iter=[0]*self.__n
            current_flow=self.__dfs(s,t,INF)
            while(current_flow):
                flow+=current_flow
                current_flow=self.__dfs(s,t,INF)

def resolve():
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    CD=[tuple(map(int,input().split())) for _ in range(n)]

    # bipartite の maximum matching で解く
    mf=Dinic(2*n+2)
    for i in range(n):
        mf.add_link(0,i+1,1)
        mf.add_link(n+i+1,2*n+1,1)
    for i in range(n):
        a,b=AB[i]
        for j in range(n):
            c,d=CD[j]
            if(a<c and b<d):
                mf.add_link(i+1,n+j+1,1)

    print(mf.flow(0,2*n+1))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
class Dinic:
    def __init__(self,n):
        self.__n=n
        self.__E=[[] for _ in range(n)]
        self.__depth=None
        self.__progress=None

    def add_link(self,u,v,w):
        self.__E[u].append([v,w,len(self.__E[v])])
        self.__E[v].append([u,0,len(self.__E[u])-1])

    def __bfs(self,s):
        depth=[-1]*self.__n
        depth[s]=0
        Q=deque([s])
        while(Q):
            v=Q.popleft()
            for nv,w,rev in self.__E[v]:
                if(w>0 and depth[nv]<0):
                    depth[nv]=depth[v]+1
                    Q.append(nv)
        self.__depth=depth

    def __dfs(self,v,t,flow):
        if(v==t): return flow
        for i in range(self.__progress[v],len(self.__E[v])):
            self.__progress[v]=i
            nv,w,rev=self.__E[v][i]
            if(w==0 or self.__depth[v]>=self.__depth[nv]): continue
            d=self.__dfs(nv,t,min(flow,w))
            if(d==0): continue
            self.__E[v][i][1]-=d
            self.__E[nv][rev][1]+=d
            return d
        return 0

    def 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,INF)
            while(current_flow):
                flow+=current_flow
                current_flow=self.__dfs(s,t,INF)

def resolve():
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    CD=[tuple(map(int,input().split())) for _ in range(n)]

    # bipartite の maximum matching で解く
    mf=Dinic(2*n+2)
    for i in range(n):
        mf.add_link(0,i+1,1)
        mf.add_link(n+i+1,2*n+1,1)
    for i in range(n):
        a,b=AB[i]
        for j in range(n):
            c,d=CD[j]
            if(a<c and b<d):
                mf.add_link(i+1,n+j+1,1)

    print(mf.flow(0,2*n+1))
resolve()

Submission status: Accepted

Solution code:
n=int(input())

ll = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])

mm=sorted([list(map(int,input().split())) for _ in range(n)])
count_num=0
for i,j in mm:
  for k,h in ll:
    if k<=i and h<=j:
      count_num+=1
      ll.remove([k,h])
      break
print(count_num)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  l1=list(map(int,input().split()))
  l.append(l1+["a",0])
for i in range(n):
  l1=list(map(int,input().split()))
  l.append(l1+["b"])
count=0
l=sorted(l)
for i in range(2*n):
  if l[i][2]=="a":
    pass
  else:#bが来たら
    num=l[i][1]
    min=100
    index=-1
    if i==0:
      pass
    else: 
      for j in range(0,i):#0~i-1までをみる
        if l[j][2]=="a":
          if l[j][3]==0:
            if min>num-l[j][1] and num>l[j][1]:
              min=num-l[j][1]
              index=j
      if index!=-1:
        l[index][3]=1
        count+=1
print(count)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    N = int(input())
    red = np.zeros([N, 2])
    blue = np.zeros([N, 2])

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

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

    blue = blue[np.argsort(blue[:, 0])]
    red = red[np.argsort(red[:, 1])[::-1]]

    d = np.zeros([N, 2])
    cnt = 0

    for i in range(N):
        d[0:N, 0:2] = blue[i, 0:2] - red[0:N, 0:2]

        if np.any((d[:, 0] > 0) & (d[:, 1] > 0)):
            dd = d[(d[:, 0] > 0) & (d[:, 1] > 0)]
            dd = dd[np.argsort(dd[:, 1])]
            ind = list(zip(*np.where(d == dd[0])))
            row = ind[0][0]
            red[row, :] = 10**9
            cnt += 1

    print(cnt)


main()

Submission status: Accepted

Solution code:
n = int(input())
list_r = [list(map(int, input().split())) for _ in range(n)]
list_b = [list(map(int, input().split())) for _ in range(n)]
list_b.sort(key=lambda x:(x[0], x[1]))

count = 0
for one_b in list_b:
  idx = -1
  max_y = -1
  for i, one_r in enumerate(list_r):
    if one_r[0] < one_b[0] and max_y < one_r[1] < one_b[1]:
      max_y = one_r[1]
      idx = i
  if idx != -1:
    count += 1
    list_r.pop(idx)
print(count)

Submission status: Accepted

Solution code:
N = int(input())
R = [[int(a) for a in input().split()] for _ in range(N)]
B = [[int(c) for c in input().split()] for _ in range(N)]

B.sort()
used = [0]*N

for i in range(N):
    y = -1
    idx = -1
    for j in range(N):
        if R[j][0] < B[i][0] and R[j][1] < B[i][1] and used[j] == 0:
            if R[j][1] > y:
                y = R[j][1]
                idx = j
                
    if idx >= 0:
        used[idx] = 1
        
print(sum(used))

Submission status: Accepted

Solution code:
N = int(input())
x = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: -x[1])
y = sorted([list(map(int, input().split())) for _ in range(N)])

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

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
A = [0] * N
B = [0] * N
for n in range(N):
  A[n] = [int(x) for x in input().split()]
for n in range(N):
  B[n] = [int(x) for x in input().split()]

B.sort(key=lambda x:x[1])
B.sort()
ans = 0
for b in B:
  A.sort(key=lambda x:x[1])
  A.sort()
  q = [a for a in A if a[0] < b[0] and a[1] < b[1]]
  q_ = [a for a in A if a[0] >= b[0] or a[1] >= b[1]]
  maxa = -1
  if q:
    for i, qq in enumerate(q):
      if qq[1] > maxa:
        maxi = i
        maxa = qq[1]
    q.pop(maxi)
    ans += 1
  A = q[:] + q_[:]

print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ab = [list(map(int, readline().split())) for _ in range(n)]
    ab = sorted(ab)
    ab = sorted(ab, key=lambda x: x[1], reverse=True)
    cd = [list(map(int, readline().split())) for _ in range(n)]
    cd = sorted(cd)
    cnt = 0
    for i in range(n):
        for j in range(n):
            if ab[i][0] <= cd[j][0] and ab[i][1] <= cd[j][1]:
                cnt += 1
                cd[j][0] = cd[j][1] = 0
                break
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

counter = 0
i = 0
while i < len(Blue):
  for j in range(len(Red)):
#    print(Blue[i], Red[j])
    if Blue[i][1] > Red[j][1] and Blue[i][0] > Red[j][0]:
#      print("removed", Blue[i], Red[j])
      Blue.remove(Blue[i])
      Red.remove(Red[j])
      counter += 1
      break
  else:
    i += 1
print(counter)

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)]
res = 0
red.sort(key=lambda x: x[1],reverse=True)
blue.sort()
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]:
            red.pop(j)
            res += 1
            break
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def FF(E, s, t):
    NN = 2*N+2
    G = [[] for _ in range(NN)]
    for a, b, f in E:
        G[a].append([b, f, len(G[b])])
        G[b].append([a, 0, len(G[a])-1])
    
    def dfs(s, t, f):
        if s == t:
            return f
        used[s] = 1
        for i, (b, _f, r) in enumerate(G[s]):
            if used[b] or _f == 0: continue
            d = dfs(b, t, min(f, _f))
            if d > 0:
                G[s][i][1] -= d
                G[b][r][1] += d
                return d
        return 0
    
    flow = 0
    while 1:
        used = [0] * NN
        f = dfs(s, t, 10**100)
        if f == 0:
            return flow
        flow += f

N = int(input())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a, b))
B = []
for _ in range(N):
    c, d = map(int, input().split())
    B.append((c, d))

E = []
for i in range(N):
    E.append((2*N, i, 1))
for i in range(N):
    E.append((N+i, 2*N+1, 1))

for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1]:
            E.append((i, N+j, 1))

print(FF(E, 2*N, 2*N+1))

Submission status: Accepted

Solution code:
#                         author:  kagemeka 
#                         created: 2019-11-06 22:04:18(JST)
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator

def main():
    n = int(sys.stdin.readline().rstrip())
    red = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
    blue = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
    reversed_b_sorted_by_a= [ab[1] for ab in sorted(red, reverse=1)]
    bd_sorted_by_ac = [acbd[1] for acbd in sorted(red + blue)]


    count = 0
    for b in reversed_b_sorted_by_a:
        b_index = bd_sorted_by_ac.index(b)
        if b_index == len(bd_sorted_by_ac) - 1:
            bd_sorted_by_ac.remove(b)
            continue
        
        range_to_scope = bd_sorted_by_ac[b_index+1:]
        possible_elements = [x for x in range_to_scope if x > b]
        if not possible_elements:
            bd_sorted_by_ac.remove(b)
            continue

        bd_sorted_by_ac.remove(min(possible_elements))
        bd_sorted_by_ac.remove(b)
        count += 1
    print(count)


if __name__ == "__main__":
    # execute only if run as a script
    main()

Submission status: Accepted

Solution code:
N = int(input())
x = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: -x[1])
y = sorted([list(map(int, input().split())) for _ in range(N)])

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

print(cnt)

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])
red.sort()
blue.sort(key=lambda x: x[1])
blue.sort()
answer = 0
for bx, by in blue:
    l = []
    for i in range(len(red)):
        rx, ry = red[i]
        if rx < bx and ry < by:
            l.append((ry, rx, i))
    if len(l) >= 1:
        l.sort(reverse=True)
        answer += 1
        red.pop(l[0][2])
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
r=[list(map(int,input().split())) for i in range(n)]
b=sorted([list(map(int,input().split())) for i in range(n)], key=lambda x:x[0])
cnt=0
for bb in b:
    t_r=[-1,-1]
    for rr in r:
        if rr[0]<bb[0] and t_r[1]<rr[1]<bb[1]:
            t_r=rr
    if t_r!=[-1,-1]:
        cnt+=1
        r.remove(t_r)
print(cnt)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ab=[]
    cd=[]
    for _ in range(n):
        ab.append(list(map(int,input().split())))
    for _ in range(n):
        cd.append(list(map(int,input().split())))
    ab.sort(reverse=True , key=lambda y:y[1])
    cd.sort(key=lambda y:y[0])
    ans=0
    for i in range(n):
        [x,y]=cd[i]
        for j in range(len(ab)):
            if x>ab[j][0] and y>ab[j][1]:
                ab.pop(j)
                ans+=1
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
V = 2*N
Red = [list(map(int, input().split())) for _ in range(N)]
Blue = [list(map(int, input().split())) for _ in range(N)]

graph = [[] for _ in range(V)]
for i in range(N):
    for j in range(N):
        a, b = Red[i]
        c, d = Blue[j]
        if a < c and b < d:
            j += N
            graph[i].append(j)
            graph[j].append(i)

match = [-1]*V # マッチングペア
used = [False]*V # DFSですでに調べたか

# search increasing path
def dfs(v):
    used[v] = True
    for nv in graph[v]:
        w = match[nv]
        if w < 0 or (not used[w] and dfs(w)):
            match[v] = nv
            match[nv] = v
            return True
    return False


def bipartite_matching():
    res = 0
    global match
    match = [-1]*V
    for v in range(V):
        if match[v] < 0:
            global used
            used = [0]*V
            if dfs(v):
                res += 1
    return res


if __name__ == '__main__':
    print(bipartite_matching())

Submission status: Accepted

Solution code:
n = int(input())
ab, cd = [], []
for _ in range(n):
    ab.append([int(x) for x in input().split()])
for _ in range(n):
    cd.append([int(x) for x in input().split()])
cd.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)
pair_cnt = 0
for cdleftmost in cd:
    for abi in ab:
        if(abi[0] < cdleftmost[0] and abi[1] < cdleftmost[1]):
            ab.remove(abi)
            pair_cnt += 1
            break
print(pair_cnt)

Submission status: Accepted

Solution code:
import bisect
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()
b.sort()

ans=0
for i in range(n):
    j=(n-1)-i
    bc,bd=list(zip(*b))
#    print(bc)
    bj_morethan_aj = bisect.bisect_left(bc, r[j][0])
    more_bi = b[bj_morethan_aj:]
    least_bd_k=-1
    least_bd=10000000
    for k in range(len(more_bi)):
        if(r[j][1] < more_bi[k][1] and more_bi[k][1] < least_bd):
            least_bd = more_bi[k][1]
            least_bd_k = k

    if(least_bd_k != -1):
        ans+=1
#        print(b[bj_morethan_aj+least_bd_k])
        del b[bj_morethan_aj+least_bd_k]
print(ans)