Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Accepted

Solution code:
N=int(input())
A,B,C,D=[0]*N,[0]*N,[0]*N,[0]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
for i in range(N):
  C[i],D[i]=map(int,input().split())
R=[0]*N
for i in range(N):
  R[i]=A[i]*1000+B[i]
B=[0]*N
for i in range(N):
  B[i]=C[i]*1000+D[i]
B.sort()
X=[0]*N
ans=0
for i in range(N):
  BX,BY=B[i]//1000,B[i]%1000
  M=-1
  for j in range(N):
    if(X[j]==0):
      RX,RY=R[j]//1000,R[j]%1000
      if(RX<BX and RY<BY):
        if(M==-1):
          M=j
        elif(RY>R[M]%1000):
          M=j
  if(M!=-1):
    X[M]=1
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
from bisect import *
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    hp = []
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 1, b])
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 0, b])
    yy = []
    ans = 0
    while hp:
        x, q, y = heappop(hp)
        if q:
            insort(yy, y)
        else:
            i = bisect_left(yy, y)
            if i > 0:
                del yy[i - 1]
                ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect

def main():
    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[0],x[1]))
    red_x = [r[0] for r in red]
    blue.sort(key= lambda x:x[0])
    answer = 0
    for i  in range(N):
        b = blue[i][0]
        max_x_index = bisect.bisect_left(red_x,b)
        search_target_red = red[:max_x_index]
        max_y = 0 
        max_index = -1

        for j,r in enumerate(search_target_red):
            if blue[i][1]>r[1]>=max_y:
                max_y = r[1]
                max_index=j
 
        if max_index!=-1:
            answer+=1
            red.pop(max_index)
            red_x.pop(max_index)
    
    print(answer)










if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
R = [(-1, -1)] * N
for n in range(N):
    x, y = map(int, input().split())
    R[n] = (x, y)
B = [(-1, -1)] * N
for n in range(N):
    x, y = map(int, input().split())
    B[n] = (x, y)

B = sorted(B)
R = sorted(R, reverse=True)

ans = 0
for i, b in enumerate(B):
    tmp = []
    for j, r in enumerate(R):
        if r[0] == -1:
            continue
        if r[0] < b[0] and r[1] < b[1]:
            tmp.append((j, r))
    if tmp:
        tmp = sorted(tmp, key=lambda x: x[1][1], reverse=True)
        R[tmp[0][0]] = (-1, -1)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
"""
出典:https://atcoder.jp/contests/abc005/tasks/abc005_3
"""
def main():
  N = int(input())
  red_l = [list(map(int,input().split())) for _ in range(N)]
  blue_l = [list(map(int,input().split())) for _ in range(N)]
  red_l=sorted(red_l,key=lambda x:-x[1])
  blue_l=sorted(blue_l,key=lambda x:x[0])

  count=0
  for r in red_l:
    for b in blue_l:
      if r[0]<b[0] and r[1]<b[1]:
        count +=1
        blue_l.remove(b)
        break
  print(count)

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
n = int(input())
lired = [list(map(int,input().split())) for _ in range(n)]
liblue = [list(map(int,input().split())) for _ in range(n)]
lired = sorted(lired,key = lambda x:-x[1])
liblue = sorted(liblue,key = lambda x:x[0])
li = list(range(n))
count = 0

for i in range(n):
  for j in li:
    if lired[i][0] < liblue[j][0] and lired[i][1] < liblue[j][1]:
      count += 1
      li.remove(j)
      break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
lired = [list(map(int,input().split())) for _ in range(n)]
liblue = [list(map(int,input().split())) for _ in range(n)]
lired = sorted(lired,key = lambda x:-x[1])
liblue = sorted(liblue,key = lambda x:x[0])
li = list(range(n))
cnt = 0
#print(lired)
#print(liblue)

for i in range(n):
  for j in li:
    if lired[i][0] < liblue[j][0] and lired[i][1] < liblue[j][1]:
      cnt += 1
      li.remove(j)
      break
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
lired = [list(map(int,input().split())) for _ in range(n)]
liblue = [list(map(int,input().split())) for _ in range(n)]
lired = sorted(lired,key = lambda x:-x[1])
liblue = sorted(liblue,key = lambda x:x[0])
li = list(range(n))
cnt = 0
#print(lired)
#print(liblue)

for i in range(n):
  for j in li:
    if lired[j][0] < liblue[i][0] and lired[j][1] < liblue[i][1]:
      cnt += 1
      li.remove(j)
      break
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N)]
AB_=sorted(AB,key=lambda x:-x[0])
CD=[list(map(int,input().split())) for _ in range(N)]
CD_=sorted(CD,key=lambda x:-x[0])
ans=0
for i in range(N):
    target=[]
    for j in range(len(CD_)):
        if CD_[j][0]>AB_[i][0] and CD_[j][1]>AB_[i][1]:
            target.append(CD_[j])
    target=sorted(target,key=lambda x:x[1])
    if len(target)==0:
        continue
    else:
        ans+=1
        CD_.remove(target[0])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    red = [[int(i) for i in input().split()] + [True] for j in range(N)]
    blue = [[int(i) for i in input().split()] for j in range(N)]

    red.sort(reverse=True)
    blue.sort()
    ans1 = 0
    for b in blue:
        for a in red:
            if a[2] and a[0] < b[0] and a[1] < b[1]:
                ans1 += 1
                a[2] = False
                break

    red.sort(key=lambda p: p[1],reverse=True)
    red = [[r0,r1,True] for r0,r1,r2 in red]
    blue.sort(key=lambda p: p[1])
    ans2 = 0
    for b in blue:
        for a in red:
            if a[2] and a[0] < b[0] and a[1] < b[1]:
                ans2 += 1
                a[2] = False
                break

    red.sort(key=lambda p: p[1],reverse=True)
    red = [[r0,r1,True] for r0,r1,r2 in red]
    blue.sort()
    ans3 = 0
    for b in blue:
        for a in red:
            if a[2] and a[0] < b[0] and a[1] < b[1]:
                ans3 += 1
                a[2] = False
                break

    red.sort(reverse=True)
    red = [[r0,r1,True] for r0,r1,r2 in red]
    blue.sort(key=lambda p: p[1])
    ans4 = 0
    for b in blue:
        for a in red:
            if a[2] and a[0] < b[0] and a[1] < b[1]:
                ans4 += 1
                a[2] = False
                break

    print(max(ans1,ans2,ans3,ans4))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n=int(input())
ab=[[int(i) for i in input().split()]for j in range(n)]
cd=[[int(i) for i in input().split()]for j in range(n)]
ab.sort()
cd.sort()

se=set()
for c,d in cd:
    li=[]
    for a,b in ab:
        if a>=c or b>=d:
            continue
        else:
            if (a,b) not in se:
                heappush(li,[-b,a])
    if li:
        b,a=heappop(li)
        se.add((a,-b))
print(len(se))

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_s = sorted(red,key=lambda x:x[1],reverse=True)
blue_s = sorted(blue)

pair = 0
for bx,by in blue_s:
  for i,(rx,ry) in enumerate(red_s):    
    if rx<bx and ry<by:
      pair +=1
      red_s.pop(i)
      break

print(pair)

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        if AB[j][2] and CD[i][2]:
            if AB[j][0] < CD[i][0]:
                if AB[j][1] < CD[i][1]:
                    ans += 1
                    AB[j][2] = False
                    CD[i][2] = False
                    break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]
ab.sort(key = lambda x: x[1] ,reverse =True)
cd.sort(key = lambda x: x[0])
ab_bool = [True]*n
cnt = 0
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 ab_bool[j]:
      cnt += 1
      ab_bool[j] = False
      break
print(cnt)

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(key=lambda x:x[0],reverse = True)
blue.sort(key=lambda x:x[1])
ans = 0
for i in range(n):
    flag = False
    for j in range(len(red)):
        if blue[i][1] > red[j][1] and blue[i][0] > red[j][0] and not flag:
            ans += 1
            red[j][0] = 100000
            flag = True
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R_dot, B_dot = [],[]
for _ in range(N):
    R_dot.append(list(map(int,input().split())) + [0])
for _ in range(N):
    B_dot.append(list(map(int,input().split())))

R_dot = sorted(R_dot, key = lambda x: x[1], reverse = True)
B_dot = sorted(B_dot, key = lambda x: x[0])

ans = 0
for i in range(N):
    for j in range(N):
        if R_dot[j][0] < B_dot[i][0] and R_dot[j][1] < B_dot[i][1] and R_dot[j][2] == 0:
            ans += 1
            R_dot[j][2] = 1
            break
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
red.sort(key=lambda x:(x[1]))
blue = sorted(list(map(int,input().split())) for _ in range(n))
blue.sort(key=lambda x:(x[0],x[1]))
seen = [False]*n
for i in range(n):
    check = -1
    for j in range(n):
        if seen[j]:continue
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
            check = j
    if check != -1:seen[check] = True
print(seen.count(True))

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()
blue.sort()

for c, d in blue:
    p = []
    dist = []
    for a, b in red:
        if a < c and b < d:
            p.append([a, b])
            dist.append(b)
        elif a >= c:
            break
    if p:
        red.remove(p[dist.index(max(dist))])

print(N - len(red))

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)]
blue.sort(key=lambda x:(x[0],x[1]))
check = [False]*n
for i in range(n):
    a = -1
    c = -1
    for j in range(n):
        if check[j]:continue
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
            if a < red[j][1]:
                a = red[j][1]
                c = j
    if c != -1:
        check[c] = True
print(check.count(True))

Submission status: Accepted

Solution code:
n = int(input())
a_b = []
for i in range(n):
    a_b.append(list(map(int, input().split())))
a_b.sort(key=lambda x: x[1], reverse=True)
c_d = []
for i in range(n):
    c_d.append(list(map(int, input().split())))
c_d = sorted(c_d)
ans = 0
for c, d in c_d:
    for a, b in a_b:
        if a < c and b < d:
            a_b.remove([a, b])
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
# 赤い点はy軸が大きい方順にソート
reds = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: -x[1])
# 青い点はx軸が小さい方順にソート
blues = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 0
for bx, by in blues:
    for rx, ry in reds:
        if rx < bx and ry < by:
            ans += 1
            reds.remove((rx, ry))
            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 = sorted(red, key=lambda x: x[1], reverse=True)
blue = sorted(blue, key=lambda x: x[0])

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

print(ans)

Submission status: Accepted

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

ab.sort()
cd.sort()

pair = []
for i in range(N):
    max_y = -1
    pair_id = -1
    for j in range(N):
        if j not in pair and cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            if max_y < ab[j][1]:
                max_y = ab[j][1]
                pair_id = j
    if pair_id != -1:
        pair.append(pair_id)

print(len(pair))

Submission status: Accepted

Solution code:
n = int(input())
p = [tuple(map(int, input().split())) for i in range(n)]
q = [tuple(map(int, input().split())) for i in range(n)]

q = sorted(q)
p = sorted(p, key=lambda x:x[1], reverse=True)
res = 0
l = [0]*n
for i in range(n):
    for j in range(n):
        if q[i][0] > p[j][0] and q[i][1] > p[j][1]:
            if l[j] == 0:
                l[j] = 1
                res += 1
                break
            else:
                continue
        
        
print(res)

Submission status: Accepted

Solution code:
n = int(input())
ab = []
cd = []
for i in range(n):
    ai, bi = map(int, input().split())
    ab.append([ai, bi])
for i in range(n):
    ci, di = map(int, input().split())
    cd.append([ci, di])

ab = sorted(ab, key=lambda x: x[1], reverse=True)
cd = sorted(cd)

count = 0
while True:
    if len(cd) == 0:
        break

    flag = 0
    for i in range(len(ab)):
        if ab[i][0] < cd[0][0] and ab[i][1] < cd[0][1]:
            flag = 1
            break

    if flag:
        ab.pop(i)
        count += 1
    cd.pop(0)

print(count)

Submission status: Accepted

Solution code:
Red  = []
Blue = []

def match_and_remove(x,y):
    maxy  = -1
    index = -1
    for i in range(len(Red)):
        rx,ry = Red[i]
        if rx < x and ry < y:
            if maxy < ry:
                maxy = ry
                index = i
    if index != -1:
        a = Red.pop(index)
        #print(a,[x,y])
        return True
    else:
        return False

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

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

ans = 0
for blue in Blue:
    x = blue[0]
    y = blue[1]
    ret = match_and_remove(x,y) 
    if ret:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
red = [(0,0) for i in range(N)]
blue = [(0,0) for i in range(N)]

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

for i in range(N):
  bx = blue[i][0]
  by = blue[i][1]
  R = len(red)
  for j in range(R):
    rx = red[R-j-1][1]
    ry = red[R-j-1][0]
    if rx < bx and ry < by:
      del red[R-j-1]
      break
      
print(N-len(red))

Submission status: Accepted

Solution code:
from operator import itemgetter
n=int(input())
A=[tuple(map(int,input().split())) for i in range(n)]
B=[tuple(map(int,input().split())) for j in range(n)]
A.sort()
B.sort()
count=0
for i in range(n):
    box=[A[j] for j in range(len(A)) if (A[j][0]<B[i][0]) and (A[j][1]<B[i][1])]
    #条件を満たす一番大きいものから消していく
    if any(box):
        box=sorted(box, key=itemgetter(1))
        A.remove(box[-1])
        count +=1
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
n=int(input())
A=[tuple(map(int,input().split())) for i in range(n)]
B=[tuple(map(int,input().split())) for j in range(n)]
A.sort()
B.sort()
count=0
for i in range(n):
    box=[A[j] for j in range(len(A)) if (A[j][0]<B[i][0]) and (A[j][1]<B[i][1])]
    if any(box):
        box=sorted(box, key=itemgetter(1))
        A.remove(box[-1])
        count +=1
print(count)

Submission status: Accepted

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    int_inputs = list(map(string_to_int, inputs))
    N = len(inputs) // 2
    reds = int_inputs[:N]
    blues = int_inputs[N:]

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

    count = 0
    for bi in range(N):
        candidates = []
        for ri in range(len(reds)):
            if blues[bi][0] > reds[ri][0] and blues[bi][1] > reds[ri][1]:
                candidates.append([ri, reds[ri][0], reds[ri][1]])
        if len(candidates) > 0:
            candidates.sort(key=lambda x: x[2])

            reds.pop(candidates[-1][0])
            count += 1

    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N*2))
    print(ret)

Submission status: Accepted

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

ans=0
for c,d in cd:
    bmax=-1
    acheck=-1
    for a,b in ab:
        if a<c and b<d:
            if b>=bmax:
                bmax=b
                acheck=a
    if acheck!=-1:
        ab.remove([acheck,bmax])
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

import queue

class Dinic:
    def __init__(self, v, inf=sys.maxsize):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to': to, 'cap': cap, 'rev': len(self.G[to])})
        self.G[to].append({'to': from_, 'cap': 0, 'rev': len(self.G[from_]) - 1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.inf)

n = int(input())
data1 = [list(map(int,input().split())) for _ in range(n)]
data2 = [list(map(int,input().split())) for _ in range(n)]
v = 2*n + 2

D = Dinic(v)
for i in range(n):
    D.add_edge(2*n,i,1)
    D.add_edge(n+i,2*n+1,1)

for i,ab in enumerate(data1):
    for j,cd in enumerate(data2):
        if ab[0]<cd[0] and ab[1]<cd[1]:
            D.add_edge(i,n+j,1)

ans = D.max_flow(2*n,2*n+1)
print(ans)

Submission status: Accepted

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

data_blue.sort()
data_red.sort(key=lambda x:x[1],reverse=True)

ans = 0
avail = [True for _ in range(n)]
for a,b in data_blue:
    for i,cd in enumerate(data_red):
        if avail[i] and cd[0] < a and cd[1] < b:
            ans += 1
            avail[i] = False
            #print(a,b,*cd)
            break

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter as get
N,*L = map(int,open(0).read().split())
L1 = L[:N*2]
L2 = L[N*2:]
R = sorted([(x,y) for x,y in zip(*[iter(L1)]*2)], key = get(1), reverse = 1)
B = sorted([(x,y) for x,y in zip(*[iter(L2)]*2)])
cnt = 0
for bx, by in B:
	for rx, ry in R:
		if rx < bx and ry < by:
			R.remove((rx,ry))
			cnt += 1
			break
print(cnt)

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(key=lambda x: x[1])
count = 0
for red in Red:
    for blue in Blue:
        if red[0]<blue[0] and red[1]<blue[1]:
            count += 1
            Blue.pop(Blue.index(blue))
            break
print(count)

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

paired = [0] * n
for a, b in red:
    for i, (c, d) in enumerate(blue):
        if a < c and b < d and not paired[i]:
            paired[i] = 1
            break

print(sum(paired))

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
N = int(input())
R = [list(map(int, input().split())) + [0] for _ in range(N)]
B = [list(map(int, input().split())) + [1] for _ in range(N)]
P = sorted(R + B, key = lambda x: (x[0], -x[1]))
res = 0
inf = 10 ** 3
Q = []
for i in range(N * 2):
  if P[i][2] == 0:
    Q.append(P[i][1])
    Q.sort()
  elif len(Q):
    j = min(bl(Q, P[i][1]), len(Q) - 1)
    if Q[j] < P[i][1]:
      res += 1
      Q.pop(j)
    elif Q[j - 1] < P[i][1]:
      res += 1
      Q.pop(j - 1)
print(res)

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

# aが大きい順に並び替え
ab = sorted(ab, reverse=True)
# dが小さい順に並び替え
cd = sorted(cd, key=lambda x: x[1])

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

Submission status: Accepted

Solution code:
import bisect
n=int(input())
ab=[[int(i) for i in input().split()] for j in range(n)]
cd=[[int(i) for i in input().split()] for j in range(n)]
ab.sort()
cd.sort()

ans=0

for c,d in cd:
    now_y=-1
    check=False
    for a,b in ab:
        if a>=c:
            break
        if b<d and b>now_y:
            now_id=bisect.bisect_left(ab,[a,b])
            now_y=b
            check=True

    if check:
        ans+=1
        ab.pop(now_id)
print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

n = int(sys.stdin.readline().strip())

red = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().strip().split())
    red.append((a, b))
red = sorted(red, reverse=True)
# pprint(red)

blue = []
for _ in range(n):
    c, d = map(int, sys.stdin.readline().strip().split())
    blue.append((c, d))
blue = sorted(blue)
# pprint(blue)

ans = 0
used = set()
for x, y in blue:
    # print("x,y:",x,y)
    # print("used")
    # pprint(used)
    tmp_red = red[:]
    cand = []
    max_j = -1
    while tmp_red:
        i, j = tmp_red.pop()
        # print("i,j:",i,j)
        if (i, j) in used:
            continue
        if i < x and j < y:
            if j > max_j:
                max_j = j
                cand = (i, j)
        if i > x:
            break
    if cand:
        ans += 1
        used.add(cand)
        # print("cand:", cand[0], cand[1])

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline


def main():
    """ main """
    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(reverse=True)
    BLUES.sort(key=itemgetter(1))

    ans = 0
    for ax,ay in REDS:
        bs = [(bx,by) for bx,by in BLUES if ax < bx and ay < by]
        if 0<len(bs):
            BLUES.remove(bs[0])
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
rs = [[0, 0] for _ in range(n)]
bs = [[0, 0] for _ in range(n)]

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

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


#rs.sort(key=lambda x: x[0]+x[1])
#bs.sort(key=lambda x: x[0]+x[1])

#print(rs)
#print(bs)

rb = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if rs[i][0]<bs[j][0] and rs[i][1]<bs[j][1]:
      rb[i].append(j)
rb.sort(key=lambda x: len(x))
#print(rb)

br = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if rs[j][0]<bs[i][0] and rs[j][1]<bs[i][1]:
      br[i].append(j)
#print(br)

use = [False]*n
ans = 0
for i in range(n):
  min_br = n+1
  min_b = n+1
  for j in rb[i]:
    if use[j]:
      continue
    if len(br[j]) <= min_br:
      min_br = len(br[j])
      min_b = j
  if min_b != n+1:
    use[min_b] = True
    ans += 1

print(ans)

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    small = [tuple(map(int, input().split())) for _ in [0]*N]
    large = [tuple(map(int, input().split())) for _ in [0]*N]
    small.sort(key=lambda x: (x[0], x[1]))
    large.sort(key=lambda x: (x[0], x[1]))
    used = [0]*N
    for l in large:
        high = -1
        idx = 0
        for i, s in enumerate(small):
            if (not used[i]) and s[0] < l[0] and s[1] < l[1]:
                if high < s[1]:
                    high = s[1]
                    idx = i
        if high != -1:
            used[idx] = 1
    print(sum(used))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

class FordFulkerson :
    # deque required
    def __init__(self, N) :
        self.N = N
        self.G = [[] for _ in range(N)]
        
    def add_edge(self, fr, to, cap) :
        self.G[fr].append([to, cap, len(self.G[to])])
        self.G[to].append([fr, 0, len(self.G[fr])-1])
        
    def bfs(self, fr, to) :
        self.pre_v = [0] * self.N
        self.pre_e = [0] * self.N
        visited = [False] * self.N
        visited[fr] = True
        
        q = deque([fr])
        while q :
            cur = q.popleft()
            
            for i, (nex, cap, _) in enumerate(self.G[cur]) :
                if visited[nex] or cap <= 0 :
                    continue
                
                self.pre_v[nex], self.pre_e[nex] = cur, i
                q.append(nex)
                visited[nex] = True
                
                if nex == to :
                    return True
                    
        return False
        
    def flow(self, fr, to) :
        ret = 0
        while self.bfs(fr, to) :
            cur = to
            min_cap = float('inf')
            while cur != fr :
                min_cap = min(min_cap, self.G[self.pre_v[cur]][self.pre_e[cur]][1])
                cur = self.pre_v[cur]
                
            ret += min_cap
            cur = to
            while cur != fr :
                self.G[self.pre_v[cur]][self.pre_e[cur]][1] -= min_cap
                self.G[cur][self.G[self.pre_v[cur]][self.pre_e[cur]][2]][1] += min_cap
                cur = self.pre_v[cur]
                
        return ret
        
FF = FordFulkerson(2 * N + 2)
for i in range(N) :
    FF.add_edge(0, i + 1, 1)
    FF.add_edge(i + N + 1, 2 * N + 1, 1)
    
for i, (a, b) in enumerate(ab) :
    for j, (c, d) in enumerate(cd) :
        if a < c and b < d :
            FF.add_edge(i + 1, j + N + 1, 1)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in cd:
    check=-1
    pair=[-1,-1]
    for j in ab:
        
        if j[0]>i[0]:
            break
        if check<j[1]<i[1]:
            check=j[1]
            pair=j
    if pair != [-1,-1]:
        ans+=1
        ab.remove(pair)
print(ans)