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:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    rs = sorted(zip(a, b))
    bs = sorted(zip(c, d))
    for bx, by in bs:
        mi = -1
        my = -1
        for i, (rx, ry) in enumerate(rs):
            if not (rx < bx and ry < by):
                continue
            if my < ry:
                mi = i
                my = ry
        if mi != -1:
            del rs[mi]
    print(N - len(rs))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (N)  # type: "List[int]"
    d = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, a, b, c, d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
inf = float('inf')

n = int(sys.stdin.readline().rstrip())
res = zip(*[map(int, sys.stdin.read().split())] * 2)
res = sorted(zip(res, [1] * n + [0] * n))

def main():
    cnt = 0
    confirmed = [0] * n * 2
    for i in range(n * 2 - 2, -1, -1):
        if not res[i][1]: continue
        yr = res[i][0][1]
        yb = inf
        k = None
        for j in range(i + 1, n * 2):
            if res[j][1] or confirmed[j]: continue
            y = res[j][0][1]
            if y > yr and y < yb:
                yb = y; k = j
        if not k: continue
        confirmed[k] = 1
        cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[1], reverse=True)
    Blues = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[0])
    used = []
    for red in Reds:
        for blue in Blues:
            if blue not in used and able_to_be_pair(red, blue):
                used.append(blue)
                break
    print(len(used))

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = [ list(myinput()) for _ in range(n) ]
cd = [ list(myinput()) for _ in range(n) ]

count = 0
for i in range(n):
    cd_sorted = mysort(cd,0)
    bx = cd[0][0]
    by = cd[0][1]
    cd.remove([bx,by])
    ab.sort(key=lambda x:x[1],reverse=True)
    # print(cd)
    # print(ab)
    for j in range(len(ab)):
        rx = ab[j][0]
        ry = ab[j][1]
        if rx<bx and ry<by:
            count += 1
            ab.remove([rx,ry])
            break
        else:
            pass
print(count)

Submission status: Accepted

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

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

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
A = [[x, y, 0] for x, y in ab]
B = [[x, y, 1] for x, y in cd]
abcd = A+B
abcd.sort()

a = []
heapify(a)
result = 0
for i in range(2*n):
    x, y, h = abcd[i]
    if h==0:
        heappush(a, -y)
    else:
        if len(a) > 0:
            a_y = heappop(a)
            h = []
            while y+a_y < 0:
                h.append(a_y)
                if len(a) > 0:
                    a_y = heappop(a)
                else:
                    break
            if y+a_y>0:
                result += 1
            for j in h:
                heappush(a, j)
        
print(result)

Submission status: Accepted

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

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

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

Submission status: Accepted

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

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

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

Submission status: Accepted

Solution code:
# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)
 
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
n = int(input())

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

edges = [set() for _ in range(n)]
matched = [-1] * n
  
for i in range(n) :
  for j in range(n) :
    if r[i][0] < b[j][0] and r[i][1] < b[j][1] :
      edges[i].add(j)
      
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(n)))

Submission status: Accepted

Solution code:
N = int(input())

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

R = sorted(R, key=lambda x: -x[1])  # 赤い点はy座標が大きい順にする
B = sorted(B, key=lambda x: x[0])  # 青い点はx座標が小さい順にする

for a, b in B:  # 青い点, x座標が小さい順になっている
    for c, d in R:  # 赤い点, y座標が大きい順になっている
        if a > c and b > d:  # 青い点のx座標より赤い点のx座標が小さく, 青い点のy座標より赤い点のy座標が小さければペアにする
            R.remove([c, d])
            break

print(N - len(R))

Submission status: Accepted

Solution code:
n = int(input())

r = [[0,0,1] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  r[i][0],r[i][1] = x,y
  
b = [[0,0,1] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  b[i][0],b[i][1] = x,y
  
r.sort(key=lambda x: x[0],reverse=True)
b.sort(key=lambda x: x[1])

ans = 0
for i in range(n) :
  for j in range(n) :
    if r[i][2] == 0 or b[j][2] == 0 :
      continue
    if r[i][0] < b[j][0] and r[i][1] < b[j][1] :
      r[i][2] = 0 ; b[j][2] = 0
      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) ]
ab = sorted(ab, key=lambda x:x[1]*(-1))
cd = sorted(cd)
ans = 0
for q in cd:
    for p in ab:
        if q[0] > p[0] and q[1] > p[1]:
            ans += 1
            ab.remove(p)
            break
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    # Dinic's algorithm
    from collections import deque
    class Dinic:
        def __init__(self, N):
            self.N = N
            self.G = [[] for i in range(N)]

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

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

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

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

        def flow(self, s, t):
            flow = 0
            INF = 10**9 + 7
            G = self.G
            while self.bfs(s, t):
                *self.it, = map(iter, self.G)
                f = INF
                while f:
                    f = self.dfs(s, t, INF)
                    flow += f
            return flow
        
    N=I()
    a=[0]*N
    b=[0]*N
    c=[0]*N
    d=[0]*N
    for i in range(N):
        a[i],b[i]=MI()
    
    for i in range(N):
        c[i],d[i]=MI()
    
    din=Dinic(2*N+2)
    for i in range(N):
        for j in range(N):
            if a[i]<c[j] and b[i]<d[j]:
                din.add_edge(1+j,1+i+N,1)
                    
    for i in range(N):
        din.add_edge(0,1+i,1)
        din.add_edge(1+i+N,2*N+1,1)
        
    print(din.flow(0,2*N+1))

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    red, blue = [-1]*2*n, [-1]*2*n

    for _ in range(n):
        a,b = map(int, input().split())
        red[a] = b
    for _ in range(n):
        a,b = map(int, input().split())
        blue[a] = b

    kouho = []
    res = 0
    for i in range(2*n-1, -1, -1):
        if blue[i] >= 0:
            kouho.append(blue[i])
        else:
            kouho.sort()
            for j in range(len(kouho)):
                if red[i] < kouho[j]:
                    kouho.pop(j)
                    res += 1
                    break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

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

used = [False]*n
A.sort()
B.sort()
count = 0
for i in range(len(B)):
    cand = [-1, -1]
    cand_idx = -1
    for j in range(len(A)):
        if A[j][0] < B[i][0]:
            # print(used[j], cand[1], A[j][1])
            if (not used[j]) and (cand[1] < A[j][1] < B[i][1]):
                cand = A[j]
                cand_idx = j
        else:
            break

    if cand_idx != -1:
        count += 1
        used[cand_idx] = True

print(count)

Submission status: Accepted

Solution code:
n = int(input())

red = [0]*n
for i in range(n):
  a, b = map(int, input().split())
  red[i] = (a, b)
red.sort()

blue = [0]*n
for i in range(n):
  c, d = map(int, input().split())
  blue[i] = (c, d)
blue.sort()

ans = 0
pair_judge = [False]*(2*n+1)
k = 0
for i in range(n):
  a, b = blue[i][0], blue[i][1]
  while True:
    if k < n and red[k][0] < a:
      pair_judge[red[k][1]] = True
      k += 1
      continue
    else:
      break
  for j in range(b-1, -1, -1):
    if pair_judge[j]:
      ans += 1
      pair_judge[j] = False
      break

print(ans)

Submission status: Accepted

Solution code:
INF=10**30
N=int(input())
ball=[list(map(int,input().split()))+['r'] for i in range(N)]
ball[len(ball):len(ball)]=[list(map(int,input().split()))+['b'] for i in range(N)]
ball.sort(key=lambda x:x[0])
cnt=0
for i in range(len(ball)):
    if(ball[i][2]=='b'):
        match=INF
        Ym=-1
        for j in range(i):
            if(ball[j][2]=='r'):
                if(ball[j][1]>Ym and ball[i][1]>ball[j][1]):
                    Ym=ball[j][1]
                    match=j
        if(match!=INF):
            ball[match][1]=INF
            cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
Red = [list(map(int,input().split())) for _ in range(N)] #赤
Blue = [list(map(int,input().split())) for _ in range(N)] #青

Red1 = sorted(Red, key=itemgetter(1),reverse = True)
Blue1 = sorted(Blue, key=itemgetter(0),reverse = False)

cnt = 0
for i in range(N):
    for j in range(N):
        if Red1[i][1] < Blue1[j][1] and  Red1[i][0] < Blue1[j][0] :
            cnt += 1
            Blue1[j][0] = -1
            break
print(cnt)

Submission status: Accepted

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

AB=sorted(ab, key=lambda x:x[1], reverse=True)
CD=sorted(cd, key=lambda x:x[0])
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] and CD[j][2] ==1:
      cnt+=1
      CD[j][2]-=1
      break
      
print(cnt)

Submission status: Accepted

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

ss = sorted(s, key=lambda x:x[1], reverse=True)
tt = sorted(t, key=lambda x:x[0])
cnt = 0

for i in range(n):
  for j in range(n):
    if ss[i][0] < tt[j][0] and ss[i][1] < tt[j][1] and tt[j][2] == 1:
      cnt += 1
      tt[j][2] -= 1
      break
    
print(cnt)

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

B.sort(key=lambda x: x[0])
# print(R)
# print(B)
ans =0
for b in B:
    candidate_R = [R[k] for k in range(len(R)) if (R[k][0] < b[0]) and (R[k][1] < b[1])] # 青い点に対する赤い点の候補
    if candidate_R:
        selected_R = sorted(candidate_R, key=lambda x:x[1])[-1]
        ans += 1
        R.remove(selected_R)
print(ans)

Submission status: Accepted

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

R.sort(reverse=True)

ans = 0
for i in range(N):
  bmin = 3 * N
  tgtb = -1
  for j in range(N):
    if (B[j][2] == 0) and (R[i][0] < B[j][0]) and (R[i][1] < B[j][1]):
      if bmin > B[j][1]:
        bmin = B[j][1]
        tgtb = j
  if tgtb != -1:
    ans += 1
    B[tgtb][2] = 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b,0])
for i in range(n):
    c,d=map(int,input().split())
    X.append([c,d,1])

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

R=[]
ans=0
for i in range(2*n):
    if X[i][2]==0:
        R.append(X[i][1])
        R.sort()
    if X[i][2]==1:
        if len(R)==0:
            continue
        if min(R)>X[i][1]:
            continue
        R.pop(bisect.bisect_left(R,X[i][1])-1)
        ans+=1
print(ans)

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

M = 2*N+2
s = 2*N
g = 2*N+1
E = [[False]*M for _ in range(M)]

for ir, (rx, ry) in enumerate(R):
    for ib, (bx, by) in enumerate(B):
        if rx<bx and ry<by:
           E[ir][ib+N] = True

for i in range(N):
    E[s][i] = True
    E[i+N][g] = True

while True:
    K = [None]*M
    K[s] = -1
    queue = [s]
    while queue and (K[g] is None):
        queue_new = []
        for q in queue:
            for e, f in enumerate(E[q]):
                if not f: continue
                if K[e] is not None: continue
                K[e] = q
                queue_new.append(e)

        queue = queue_new

    #print(K)
    #input("aa")

    if K[g] is None:
        break
    else:
        i = g
        while K[i]!=-1:
            #print(i,end=' ')
            E[K[i]][i] = False
            E[i][K[i]] = True
            i = K[i]

ans = 0
for ir in range(N):
    if not E[s][ir]: 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)]

from operator import itemgetter

red=sorted(red,key=itemgetter(1))
blue=sorted(blue,key=itemgetter(0))
red=red[::-1]
#print(red)
#print(blue)
seen=[0]*n
ans=0
for i in range(n):#blue
    for j in range(n):#red
        if seen[j]==0 and red[j][0]<blue[i][0] and red[j][1]<blue[i][1]:
            seen[j]=1
            ans+=1
            break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
r = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
r.sort()
b.sort()
s = []
k = 0
ans = 0
for i in range(n):
    while True:
        if k >= n:
            break
        if b[i][0] > r[k][0]:
            s.append(r[k][1])
            k += 1
        else:
            s.sort()
            break
    for j in range(len(s) - 1, -1, -1):
        if s[j] < b[i][1]:
            ans += 1
            s.remove(s[j])
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [[0, 0, 0]for _ in range(2*N)]
for i in range(N):
    x, y = map(int, input().split())
    P[i] = [0, x, y]
for i in range(N):
    x, y = map(int, input().split())
    P[N+i] = [1, x, y]
P.sort(key=lambda x: x[1])
cnt = 0
for i in range(2*N):
    if P[i][0] == 0:
        continue
    else:
        if i == 0:
            continue
        else:
            M = [-1, -1]
            for j in range(i):
                if P[j][0] == 0:
                    if P[j][2] > M[1] and P[j][2] < P[i][2]:
                        M = [j, P[j][2]]
            if M[0] != -1:
                cnt += 1
                P[M[0]][0] = 2
print(cnt)

Submission status: Accepted

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

cnt=0
for a,b in AB[::-1]:
    for i,j in enumerate(CD):
        c,d=j
        if a<c and b<d:
            cnt +=1
            del CD[i]
            break
print(cnt)

Submission status: Accepted

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

A.sort()
B.sort()

cnt = 0
for u, v in B:
    maxy = -1
    maxi = -1

    for i, (x, y) in enumerate(A):

        if x >= u:
            break
        if y >= v:
            continue

        if maxy < y:
            maxy = y
            maxi = i

    if maxy > -1:
        A.pop(maxi)
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 091
# C - 2D Plane 2N Points
# https://atcoder.jp/contests/abc091/tasks/arc092_a

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
B = [tuple(map(int, input().split())) for _ in range(N)]

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

used = [False]*N

cnt = 0
for u, v in B:
    maxy = -1
    maxi = -1

    for i, (x, y) in enumerate(A):

        if x >= u:
            break
        if used[i] or y >= v:
            continue

        if maxy < y:
            maxy = y
            maxi = i

    if maxy > -1:
        used[maxi] = True
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans = 0

for i in B:
    dis = -1
    check = -1
    for j in range(len(A)):
        if i[0] > A[j][0] and i[1] > A[j][1]:
            
            if dis < A[j][1]:
                check = j
                dis = A[j][1]
    if check > -1:
        ans += 1
        A.pop(check)

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

from operator import itemgetter
red = sorted(red, reverse=True)
blue = sorted(blue, key=itemgetter(1))

seen = [0] * N
ans = 0
for i in range(N):
    for j in range(N):
        if seen[j] == 0 and red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            seen[j] = 1
            ans += 1
            break

print(ans)

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

from operator import itemgetter
ab.sort(key=itemgetter(1))
cd.sort(key=itemgetter(0))

C = [0] * N
cnt = 0
for i in range(N):
    for j in range(N):
        if C[j] == 0 and ab[- j - 1][0] < cd[i][0] and ab[ - j - 1][1] < cd[i][1]:
            C[j] = 1
            cnt += 1
            break
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
A=[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])
A.sort(key=lambda x:x[1])
C=[0]*N
cnt=0
for i in range(N):
  for j in range(N):
    if C[j]==0 and A[-i-1][0]<B[j][0] and A[-i-1][1]<B[j][1]:
      C[j]=1
      cnt+=1
      break
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
reds=[]
for _ in range(N):
    red=[]
    a,b=map(int,input().split())
    red.append(b)
    red.append(a)
    reds.append(red)
blues=[]
for _ in range(N):
    blue=[]
    c,d=map(int,input().split())
    blue.append(c)
    blue.append(d)
    blues.append(blue)
reds2=sorted(reds)
blues2=sorted(blues)
answer=0
for b in blues2:
    A=[a for a in reds2 if a[1]<b[0] and a[0]<b[1]]
    if len(A)==0:
        continue
    else:
        delete=A[-1]
        reds2.remove(delete)
        answer+=1
print(answer)

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

def sortx(xy):
  return xy[0]
def sorty(xy):
  return -xy[1]

AB.sort(key=sorty)
CD.sort(key=sortx)

count = 0

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

print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = [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])
a.sort(key=lambda x: x[1])
seen = [0]*n
count = 0

for i in range(n):
  for j in range(n):
    if (seen[j] == 0) and (a[-(i+1)][0] < b[j][0]) and (a[-(i+1)][1] < b[j][1]):
      seen[j] = 1
      count = count + 1
      break
      
print(count)

Submission status: Accepted

Solution code:
N = int(input())

ARR = []
for i in range(N):
    ARR.append([int(s) for s in input().split(" ")])

CRR = []
for i in range(N):
    CRR.append([int(s) for s in input().split(" ")])


def calculate(n, arr, crr):

    reds = sorted(arr,key=lambda x:-x[1])
    blues = sorted(crr,key=lambda x:x[0])
    counts = 0

    for i,bl in enumerate(blues):
        for j,rd in enumerate(reds):

            if (rd[0] < bl[0]) and (rd[1] < bl[1]):
                counts = counts + 1
                reds[j][1] = 1000
                reds[j][0] = 1000
                break
    print(counts)

calculate(N, ARR, CRR)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N)]
    CD = [list(map(int, input().split())) for _ in range(N)]

    reds = sorted(AB, key=lambda x: x[1], reverse=True)
    blues = sorted(CD, key=lambda x: x[0])
    cnt = 0

    for blue in blues:
        for red in reds:
            if red[0] < blue[0] and red[1] < blue[1]:
                red[1] = float("inf")
                cnt += 1
                break
    print(cnt)


if __name__ == "__main__":
    main()

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 = [tuple(map(int, input().split())) for _ in range(N)]
blue = [tuple(map(int, input().split())) for _ in range(N)]

red.sort(reverse=True)

cnt = 0
track = [0] * N
for r in red:
    y = 2 * N + 1
    p = -1
    for i, b in enumerate(blue):
        if track[i] == 0:
            if b[0] > r[0] and b[1] > r[1] and b[1] < y:
                y = b[1]
                p = i
    if p >= 0:
        track[p] = 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

c.sort()
a.sort(key=lambda x:x[1])
#a.reverse()

icnt=0
ic2=0
for ic in range(len(c)):
    for ia in range(len(a)-1,-1,-1):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            icnt=icnt+1
            del a[ia]
            break
        else:
            continue
        break

print(icnt)

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])
cnt=0
r_used=[False]*n
for i in range(n):
  bx,by=b[i][0],b[i][1]
  max_y=-1
  idx=-1
  for j in range(n):
    if r[j][0]<bx and r[j][1]<by and max_y<r[j][1] and not r_used[j]:
      idx=j
      max_y=r[j][1]
  if idx>=0:
    r_used[idx]=True
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
r = [tuple(map(int, input().split())) for i in range(n)]
b = [tuple(map(int, input().split())) for i in range(n)]

r = sorted(r, key=itemgetter(1), reverse=True)
b.sort()

pair = [False]*n

for i in range(n):
    for j in range(n):
        if b[i][0] > r[j][0] and b[i][1] > r[j][1] and pair[j] == False:
            pair[j] = True
            break

print(sum(pair))

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
r = [tuple(map(int, input().split())) for i in range(n)]
b = [tuple(map(int, input().split())) for i in range(n)]

r = sorted(r, key=itemgetter(1), reverse=True)
b.sort()

ans = 0
pair = [False]*n

for i in range(n):
    for j in range(n):
        if b[i][0] > r[j][0] and b[i][1] > r[j][1] and pair[j] == False:
            pair[j] = True
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:

def Plane_2N(n, abli, cdli):

    ans = 0
    count = [0]*n

    abli.sort(key=lambda x: - x[1])
    cdli.sort()

    for i in cdli:
        for w in range(n):
            if abli[w][0] < i[0] and abli[w][1] < i[1] and count[w] == 0:
                ans += 1
                count[w] = 1
                break

    return ans

def main():
    n = int(input())
    abli = [list(map(int, input().split())) for i in range(n)]
    cdli = [list(map(int , input().split())) for i in range(n)]
    print(Plane_2N(n , abli , cdli))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

red.sort(key=lambda x: x[1])
blue.sort()
is_paird = [0] * n
cnt = 0

for b in blue:
    idx = -1
    for i, r in enumerate(red):
        if not is_paird[i] and r[0] < b[0] and r[1] < b[1]:
            idx = i
    if idx != -1:
        is_paird[idx] = 1
        cnt += 1

print(cnt)