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())
R = [0]*n
B = [0]*n
for i in range(n): R[i] = [int(j) for j in input().split()]
for i in range(n): B[i] = [int(j) for j in input().split()]
flag = [False]*n
R.sort(key=lambda x:x[1],reverse=True)
B.sort(key=lambda x:x[0])
ans = 0
for i in range(n):
    c,d = B[i]
    for j in range(n):
        if flag[j]: continue 
        a,b = R[j]
        if c > a and d > b:
            ans += 1
            flag[j] = True
            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)]
b.sort(key=lambda x:x[0])
p=[]
r_used=[0]*n
for i in range(n):
    q=[]
    for j in range(n):
        if r[j][0]<b[i][0] and r[j][1]<b[i][1]:
            q.append([r[j][1],j])
    q.sort(key=lambda x:x[0],reverse=True)
    p.append(q)
ans = 0
for i in range(n):
    for j in range(len(p[i])):
        if p[i][j][0]<b[i][1] and r_used[p[i][j][1]]==0:
            ans+=1
            r_used[p[i][j][1]]=1
            break
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, *abcd = map(int, open(0).read().split())
    red = list(zip(abcd[0:2 * n + 1:2], abcd[1:2 * n + 1:2]))
    blue = list(zip(abcd[2 * n::2], abcd[2 * n + 1::2]))

    r = sorted(red, key=lambda p: p[1], reverse=True)
    b = sorted(blue)
    r = tuple(r)
    b = tuple(b)
    ans = 0
    done = []
    for xb, yb in b:
        for xr, yr in r:
            if xr < xb and yr < yb:
                if [xr, yr] not in done:
                    done.append([xr, yr])
                    ans += 1
                    break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, *abcd = map(int, open(0).read().split())
    red = list(zip(abcd[0:2 * n + 1:2], abcd[1:2 * n + 1:2]))
    blue = list(zip(abcd[2 * n::2], abcd[2 * n + 1::2]))

    r = sorted(red, key=lambda p: p[1], reverse=True)
    b = sorted(blue)
    ans = 0
    done = []
    for xb, yb in b:
        for xr, yr in r:
            if xr < xb and yr < yb:
                if [xr, yr] not in done:
                    done.append([xr, yr])
                    ans += 1
                    break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(N):
    AB[i] = (AB[i][0] + 1000000, AB[i][1])
    CD[i] = (CD[i][0] + 1000000, CD[i][1])

AB.sort(key = max, reverse = True)
CD.sort(key = min)



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

print(counter)

Submission status: Accepted

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

AB.sort(key = max, reverse = True)
CD.sort(key = min)

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

print(counter)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)]
B = [tuple(map(int, input().split())) for _ in range(N)]
R = sorted(R, key=itemgetter(1), reverse=True)
B = sorted(B, key=itemgetter(0))

count = 0
for c, d in B:
    for a, b in R:
        if (a < c) & (b < d):
            count += 1
            R.remove((a, b))
            break
print(count)

Submission status: Accepted

Solution code:
n=int(input())
ab=list()
cd=list()
for i in range(n):
    ab.append(list(map(int,input().split())))
for j in range(n):
    cd.append(list(map(int,input().split())))
cd.sort(key=lambda x:x[0])
AB=[[-1,-1]]*n
for i in range(n):
    S=[x for x in ab if x[0]<cd[i][0] and x[1]<cd[i][1]]
    S.sort(key=lambda k:k[1])
    if len(S)>0:
        AB[i]=S[-1]
        ab.remove(S[-1])
print(len(AB)-AB.count([-1,-1]))

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
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

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
R = [tuple(map(int,input().split())) for _ in range(N)]
B = [tuple(map(int,input().split())) for _ in range(N)]

# 0 : start
# 1..N : 赤
# N+1..2N: 青
# 2N+1 : end
dinic = Dinic(N*2+2)

# 始点 -> 赤
for i in range(N):
    dinic.add_edge(0,i+1,1)
# 青 -> 終点
for i in range(N):
    dinic.add_edge(N+i+1,N*2+1,1)
# 条件を満たす 赤 -> 青 
for i in range(N):
    for j in range(N):
        rx,ry = R[i]
        bx,by = B[j]
        if rx < bx and ry < by:
            dinic.add_edge(i+1,N+j+1,1)

print(dinic.flow(0,N*2+1))

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    ab=[0]*n
    for i in range(n):
        ab[i]=list(map(int,readline().split()))
    cd=[0]*n
    for i in range(n):
        cd[i]=list(map(int,readline().split()))

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

    res=0
    m=-1
    for i in range(n):
        c=cd[m][0]
        d=cd[m][1]
        now=-1
        key=-1
        for j in range(len(ab)):
            a=ab[j][0]
            b=ab[j][1]
            if a<c:
                if b<d and now<b:
                    now=b
                    key=j
            else:
                break
        if key>=0:
            res+=1
            ab.pop(key)
            cd.pop(m)
        else:
            m-=1
    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    red = []
    blue = []
    for i in range(n):
        a, b = map(int, input().split())
        red.append((a, b))
    for i in range(n):
        c, d = map(int, input().split())
        blue.append((c, d))
    red.sort(key=lambda x: x[1], reverse=True)
    blue.sort()
    ans = 0
    for i in range(n):
        for j in range(len(red)):
            a, b, c, d = red[j][0], red[j][1], blue[i][0], blue[i][1]
            if a < c and b < d:
                ans += 1
                del red[j]
                break
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
cnt = 0
dic = defaultdict(list)
ab = []
cd = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
for i in range(n):
    c, d = map(int, input().split())
    cd.append((c, d))
for i in ab:
    for j in cd:
        a, b = i
        c, d = j
        if a < c and b < d:
            dic[i].append(j)
seen = set()
for key, value in sorted(dic.items(), key=lambda x: x[0][1], reverse=True):
    for co in sorted(value, key=lambda x: x[0]):
        if co not in seen:
            cnt += 1
            seen.add(co)
            break
print(cnt)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter

def main():
    N = int(readline())
    R = [tuple(map(int, readline().rstrip().split())) for _ in range(N)]
    B = [tuple(map(int, readline().rstrip().split())) for _ in range(N)]

    B.sort(key=itemgetter(0))
    R.sort(key=itemgetter(1), reverse=True)
    ans = 0
    for c, d in B:
        for a, b in R:
            if a < c and b < d:
                ans += 1
                R.remove((a, b))
                break
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
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[1], reverse=True)
b.sort()
for bi in b:
  for i in range(len(r)):
    if r[i][0] < bi[0] and r[i][1] < bi[1]:
      r = r[:i] + r[i+1:]
      break
print(n - len(r))

Submission status: Accepted

Solution code:
# 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]

N=int(input())
pro=HopcroftKarp(N,N)
point0=[]
for i in range(0,N):
    a,b=map(int,input().split())
    point0.append((a,b))

point1=[]
for i in range(0,N):
    c,d=map(int,input().split())
    point1.append((c,d))

for i in range(0,N):
    for j in range(0,N):
        a,b=point0[i]
        c,d=point1[j]
        if a<c and b<d:
            pro.add_edge(i,j)

print(pro.flow())

Submission status: Accepted

Solution code:
N = int(input())
R = []
B = []
for _ in range(N):
    R.append(list(map(int,input().split())))
for _ in range(N):
    B.append(list(map(int,input().split())))
B.sort()
flag = [1 for i in range(N)]
ans = 0
for i in range(N):
    MAX = -1
    index = -1
    for j in range(N):
        if flag[j] and R[j][0] < B[i][0] and R[j][1] < B[i][1] and MAX < R[j][1]:
            MAX = R[j][1]
            index = j
    if index == -1:
        continue
    flag[index] = 0
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

ans = 0
used = [False]*n
ab.sort(key = lambda x: x[1])
ab.sort(key = lambda x: x[0])
cd.sort(key = lambda x: x[1])
cd.sort(key = lambda x: x[0])

for i in range(n):
    c,d = cd[i]
    li = []
    for j in range(n):
        if ab[j][0] < c and ab[j][1] < d and not used[j]:
            li.append((ab[j], j))
    max_idx = 0
    max_tmp = -1
    if li:
        for j in li:
            if max_tmp < j[0][1]:
                max_tmp = j[0][1]
                max_idx = j[1]
        ans += 1
        used[max_idx] = True

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

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


output=0

for blue in bluelist:
	for red in redlist:
		if blue[1] > red[1] and blue[0] > red[0]:
			output+=1
			redlist.remove(red)
			break

print(output)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

red.sort()
blue.sort(key=itemgetter(1))

ans = 0
for i in range(n):
    a,b = red[-i-1]
    for j in range(len(blue)):
        c,d = blue[j]
        if a<c and b<d:
            ans += 1
            blue[j]=[0,0]
            break
print(ans)

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)])
a=0
for i in range(n):
  y=-1
  c=-1
  for j in range(n-a):
    if R[j][0]<B[i][0] and R[j][1]<B[i][1]:
      if R[j][1]>y:
        y=R[j][1]
        c=j
  if c==-1:
    continue
  else:
    R.pop(c)
    a=a+1
print(a)

Submission status: Accepted

Solution code:
n=int(input())
R=set([tuple(map(int,input().split())) for i in range(n)])
B=[tuple(map(int,input().split())) for i in range(n)]
B.sort()
ans=0
for a,b in B:
    x,y=-1,-1
    for c,d in R:
        if c<a and d<b and y<d:
            x,y=c,d
    if x>-1:
        ans+=1
        R.remove((x,y))
print(ans)

Submission status: Accepted

Solution code:
    #できなかった
n=int(input())
r=sorted([list(map(int,input().split())) for i in range(n)])
b=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for bx,by in b:
    ypoint=-1
    index=-1
    for num,(rx,ry) in enumerate(r):
        if bx>rx and by>ry and ypoint < ry:
            ypoint=ry
            index =num
    if ypoint>=0:
        ans+=1
        r.pop(index)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
ab = [list(map(int, readline().split())) for _ in range(n)]
cd = [list(map(int, readline().split())) for _ in range(n)]
cd.sort()
cnt = 0
for c, d in cd:
    memo = []
    for i, (a, b) in enumerate(ab):
        if c > a and d > b:
            memo.append([i, b])
    if memo:
        cnt += 1
        memo.sort(key=lambda x: -x[1])
        ab.pop(memo[0][0])
print(cnt)

Submission status: Accepted

Solution code:
# 解説AC
import sys
input = sys.stdin.readline
n=int(input())
R=[list(map(int,input().split())) for i in range(n)]
B=sorted([tuple(map(int,input().split())) for i in range(n)])
ans=0
for i in range(n):
    a,b=B[i][0],B[i][1]
    y=-1
    ind=-1
    for j in range(n):
        c,d=R[j][0],R[j][1]
        if c<a and d<b and y<d:
            ind=j
            y=d
    if ind>=0:
        ans+=1
        R[ind][0]=1000
        R[ind][1]=1000
print(ans)

Submission status: Accepted

Solution code:

n=int(input())
r=[[0]*3 for i in range(n)]
b=[[0]*2 for i in range(n)]
for i in range(n):
    r[i]=list(map(int,input().split()))+[0]
for i in range(n):
    b[i]=list(map(int,input().split()))

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

psum=0
for i in range(n):
    for ii in range(n):
#        print("b:",i,b[i][0],b[i][1],"r:",ii,r[ii][0],r[ii][1])
        if b[i][0]>r[ii][0] and b[i][1]>r[ii][1] and r[ii][2]==0:
            r[ii][2]=1
            psum+=1
            break
print(psum)

Submission status: Accepted

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

for c,d in B:
  i,mv,mi=0,-1,0
  for i,(a,b) in enumerate(R):
    if a<c:
      if b<d and U[i]==0 and mv<b:
        mv,mi=b,i
    else:
      break
  if mv!=-1:
    U[mi]=1

print(sum(U))

Submission status: Accepted

Solution code:
N=int(input())
R=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0])
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0])
U=[0]*N

for c,d in B:
  i,mv,mi=0,-1,0
  for a,b in R:
    if a<c:
      if b<d and U[i]==0:
        if mv<b:
          mv,mi=b,i
      i+=1
    else:
      break

  if mv!=-1:
    U[mi]=1

print(sum(U))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

def gen_graph(s, t, n, m):
    graph = [[] for _ in range(n + m + 2)]
    def add_edges(u, v, c):
        graph[u].append([v, c, len(graph[v])])
        graph[v].append([u, 0, len(graph[u]) - 1])

    for i in range(n):
        add_edges(s, i, 1)
    
    for i in range(m):
        add_edges(i + n, t, 1)
        
    for i, (a, b) in enumerate(X):
        for j, (c, d) in enumerate(Y):
            if a < c and b < d:
                add_edges(i, j + n, 1)
                
    return graph


def dfs(u, t, f):
    if u == t:
        return f
    
    used[u] = True
    for i in range(len(graph[u])):
        v, c, r = graph[u][i]
        if not used[v] and c > 0:
            d = dfs(v, t, min(f, c))
            if d > 0:
                graph[u][i][1] -= d
                graph[v][r][1] += d
                return d

    return 0


s = 2 * N
t = s + 1
graph = gen_graph(s, t, N, N)
flow = 0
while True:
    used = [False] * (2 * N + 2)
    f = dfs(s, t, 10 ** 9 + 7)
    flow += f
    if f == 0:
        break
        
print(flow)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n = ni()
    red = []
    for _ in range(n):
        red.append(nl())
    blue = []
    for _ in range(n):
        blue.append(nl())

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

    #print(red, blue)
    ans = 0
    for _ in range(n):
        mn = blue.pop()
        for i in range(len(red)):
            if mn[0] > red[i][0] and mn[1] > red[i][1]:
                #print(mn, red.pop(i), 'pair')
                red.pop(i)
                ans += 1
                break

    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    used = []
    for i in range(n):
        for j in range(n):
            if (R[j] not in used) and (R[j][0] < B[i][0]) and R[j][1] < B[i][1]:
                used.append(R[j])
                break
    print(len(used))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# solution

import io
import sys

data=int(input())

array=[list(map(int,input().split())) for i in range(data) ]

are=[list(map(int,input().split()))  for i in range(data) ]

array.sort(key=lambda x:x[1],reverse=1)

are.sort()

result=0

for b in are:
    for r in array:
        if b[1]>r[1] and b[0]>r[0]:
            result+=1
            array.remove(r)
            break
print(result)

Submission status: Accepted

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

red.sort(reverse=True)
blue.sort()

ans = 0
for i in range(n):
    x = red[i][0]
    y = red[i][1]
    index = -1
    now_by = 201
    for j in range(len(blue)):
        if x < blue[j][0] and y < blue[j][1] and now_by > blue[j][1]:
            index = j
            now_by = blue[j][1]
    if index >= 0:
        ans += 1
        blue.pop(index)


print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    red = sorted([tuple(map(int, input().split())) for _ in range(N)], key = lambda x:(-x[1], x[0]))
    blue = sorted([tuple(map(int, input().split())) for _ in range(N)])

    available = [True] * N

    ans = 0
    for bx, by in blue:
        for i, (rx, ry) in enumerate(red):
            if bx > rx and by > ry and available[i]:
                ans += 1
                available[i] = False
                break
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [[0]*2 for _ in range(N)]
C = [[0]*2 for _ in range(N)]
for i in range(N):
    A[i][0],A[i][1] = map(int,(input().split()))
for i in range(N):
    C[i][0],C[i][1] = map(int,(input().split()))
    
C.sort()
ans = 0
for i in range(N):
    nim = 100000
    for j in range(len(A)):
        if A[j][0] < C[i][0]:
            tmp = C[i][1] - A[j][1]
            if 0 < tmp < nim:
                nim = tmp
                sa = j
    if nim != 100000:
        del A[sa]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())

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

    from operator import itemgetter

    red.sort()
    blue.sort()

    ans = 0

    for bx, by in blue:
        ry_max = -1
        r_idx = -1

        for ri, ele in enumerate(red):
            rx = ele[0]
            ry = ele[1]
            if rx < bx and ry < by:
                if ry > ry_max:
                    ry_max = ry
                    r_idx = ri

        if r_idx != -1:
            del red[r_idx]
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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)]
ans = 0
dp_ab = [False] * n
dp_cd = [False] * n

ab.sort(key = itemgetter(1), reverse = True)
cd.sort()

for i in range(n):
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and dp_cd[i] == False and dp_ab[j] == False:
            dp_cd[i] = True
            dp_ab[j] = True
            ans += 1

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)]

que = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
      que[j].append(i)

def dfs(i,v):
  
  for a in que[i]:
    if a in v:
      continue
    v.add(a)
    if ab[a] == -1 or dfs(ab[a], v):
      ab[a] = i
      return True
  return False
      
v = [set() for _ in range(n)]   
ab = [-1]*n

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

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 = sorted(ab, key = lambda x:x[0], reverse = True)
cd_sorted = sorted(cd, key = lambda x:x[0], reverse = True)


for i in range(len(ab_sorted)):
    candidate = -10e+10
    minimum_size = 10e+10
    for j in range(len(cd_sorted)):
        if cd_sorted[j][0] > ab_sorted[i][0] and cd_sorted[j][1] > ab_sorted[i][1] and minimum_size > cd_sorted[j][1]:
            candidate = j
            minimum_size = cd_sorted[j][1]
    if candidate != -10e+10:
        del cd_sorted[candidate]
print(len(ab_sorted) - len(cd_sorted))

Submission status: Accepted

Solution code:
N=int(input())

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

#print(red_list)
#print(blue_list)

answer=0
selected_set=set()
for i in range(N):
  c,d=blue_list[i]
  max_y=-1
  maxarg_y=-1
  for j in range(N):
    a,b=red_list[j]
    if c<=a:
      break
    
    if b<d and b>max_y and not j in selected_set:
      max_y=b
      maxarg_y=j
      
  if maxarg_y!=-1:
    answer+=1    
    selected_set.add(maxarg_y)
    #print(red_list[maxarg_y],blue_list[i])
    
print(answer)

Submission status: Accepted

Solution code:
N=int(input())

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

#print(red_list)
#print(blue_list)

answer=0
selected_set=set()
for i in range(N):
  c,d=blue_list[i]
  max_y=-1
  maxarg_y=-1
  for j in range(N):
    a,b=red_list[j]
    if c<=a:
      break
    
    if b<d and b>max_y and not j in selected_set:
      max_y=b
      maxarg_y=j
      
  if maxarg_y!=-1:
    answer+=1    
    selected_set.add(maxarg_y)
    #print(red_list[maxarg_y],blue_list[i])
    
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
r = sorted([list(map(int, input().split())) for i in range(n)])
b = sorted([list(map(int, input().split())) for i in range(n)])
ans = 0
for bx,by in b:
  now_ry = -1
  now_index = -1
  for key,(rx,ry) in enumerate(r):
    if bx > rx and by > ry and ry > now_ry:
      now_ry = ry
      now_index = key
  if now_ry >= 0:
    ans += 1
    r.pop(now_index)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ab=[[int(i) for i in input().split()] for _ in range(n)]
cd=[[int(i) for i in input().split()] for _ in range(n)]
inab=[sum(map(lambda x:x[0]>a and x[1]>b,cd)) for a,b in ab]
incd=[sum(map(lambda x:x[0]<c and x[1]<d,ab)) for c,d in cd]
ans=0
while 1:
  f=1
  mab=1000
  for i in range(n):
    if inab[i] > 0 and mab > inab[i]:
      f=0
      mab=inab[i]
  if f:
    break
  mcd=1000
  tmp=(-1,-1)
  ans+=1
  for i in range(n):
    if mab==inab[i]:
      a,b=ab[i]
      for j in range(n):
        if incd[j]==0:continue
        c,d=cd[j]
        if a<c and b<d and mcd>incd[j]:
          mcd=incd[j]
          tmp=(i,j)
  ta,tb=ab[tmp[0]]
  tc,td=cd[tmp[1]]
  inab[tmp[0]]=0
  incd[tmp[1]]=0
  for i in range(n):
    a,b=ab[i]
    c,d=cd[i]    
    if inab[i]:
      if a<tc and b<td:
        inab[i]-=1
    if incd[i]:
      if c>ta and d>tb:
        incd[i]-=1  
print(ans)

Submission status: Accepted

Solution code:
"abc091c - 2D Plane 2N Points"
N = int(input())
reds = [list(map(int, input().split())) for _ in range(N)]
blues = [list(map(int, input().split())) for _ in range(N)]

# 赤い点をy座標による降順ソートする
reds.sort(key=lambda x: -x[1])
# 青い点をx座標による昇順ソートする
blues.sort(key=lambda x: x[0])
# 一番左側の青い点からマッチング相手を探していく
for c, d in blues:
    for a, b in reds:
        if a <= c and b <= d:
            reds.remove([a, b])
            break
print(N-len(reds))