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: Runtime Error

Solution code:
n = int(input())
red = []
red_x = []
blue = []
blue_y = []
for i in range(n):
    a, b = map(int,input().split())
    red.append([a,b])
    red_x.append(a)
    
for i in range(n):
    c, d = map(int,input().split())
    blue.append([c,d])
    blue_y.append(d)

count = 0    
for i in range(n):
    p = max(red_x)
    s = min(blue_y)
    q = 0
    r = 0
    jjj = 0
    kkk = 0
    for j in range(n):
        if red[j][0] == p:
            q = red[j][1]
            jjj = j
    for k in range(n):
        if blue[k][1] == s:
            r = blue[k][0]
            kkk = k
            
    if p < r and q < s:
        count = count + 1 
        red_x.remove(p)
        blue_y.remove(s)
        red.remove(red[jjj])
        blue.remove(ble[kkk])


    else:
        None
        
print(count)

Submission status: Runtime Error

Solution code:
n  = int(input())
red = []
red_x = []
blue = []
blue_y = []
for i in range(n):
    a, b = map(int,input().split())
    red.append([a,b])
    red_x.append(a)
    
for i in range(n):
    c, d = map(int,input().split())
    blue.append([c,d])
    blue_y.append(d)

count = 0    
for i in range(n):
    p = max(red_x)
    s = min(blue_y)
    q = 0
    r = 0
    jjj = 0
    kkk = 0
    for j in range(n):
        if red[j][0] == p:
            q = red[j][1]
            jjj = j
    for k in range(n):
        if blue[k][1] == s:
            r = blue[k][0]
            kkk = k
            
    if p < r and q < s:
        count = count + 1 
        red_x.remove(p)
        blue_y.remove(s)
        red.remove(red[jjj])
        blue.remove(ble[kkk])


    else:
        None
        
print(count)

Submission status: Runtime Error

Solution code:
 n  = int(input())
red = []
red_x = []
blue = []
blue_y = []
for i in range(n):
    a, b = map(int,input().split())
    red.append([a,b])
    red_x.append(a)
    
for i in range(n):
    c, d = map(int,input().split())
    blue.append([c,d])
    blue_y.append(d)

count = 0    
for i in range(n):
    p = max(red_x)
    red_x.remove(p)
    s = min(blue_y)
    blue_y.remove(s)
    q = 0
    r = 0
    for j in range(n):
        if red[j][0] == p:
            q = red[j][1]
            red[j][0] = -1
            red[j][1] = -1
    for k in range(n):
        if blue[k][1] == s:
            r = blue[k][0]
            blue[k][0] = -1
            blue[k][1] = -1
            
    if p < r and q < s:
        count = count + 1 
    else:
        None
        
print(count)

Submission status: Runtime Error

Solution code:
n  = int(input())
red = []
red_x = []
blue = []
blue_y = []
for i in range(n):
    a, b = map(int,input().split())
    red.append([a,b])
    red_x.append(x)
    
for i in range(n):
    c, d = map(int,input().split())
    blue.append([c,d])
    blue_y.append(d)

count = 0    
for i in range(n):
    p = max(red_x)
    red_x.remove(p)
    s = max(blue_y)
    blue_y.remove(s)
    q = 0
    r = 0
    for j in range(n):
        if red[j][0] == p:
            q = red[j][1]
            red[j][0] = -1
            red[j][1] = -1
    for k in range(n):
        if blue[k][1] == s:
            r = blue[k][0]
            blue[k][0] = -1
            blue[k][1] = -1
            
    if p < r and q < s:
        count = count + 1
    else:
        None

Submission status: Runtime Error

Solution code:
def comp(p, q):
    if p[0]<q[0] and p[1]<q[1]:
        return True
    else:
        return False
 
n=int(input())
r=sorted([list(map(lambda x:int(x), input().split())) for _ in range(n)])
b=sorted([list(map(lambda x:int(x), input().split())) for _ in range(n)])
rp=n-1
bp=n-1
count=0
for y in reversed(b):
    for x in reversed(r):
	if comp(x, y):
            count+=1
            r.remove(x)
print(count)

Submission status: Runtime Error

Solution code:
def comp(p, q):
    if p[0]<q[0] and p[1]<q[1]:
        return True
    else:
        return False

n=int(input())
r=sorted([list(map(lambda x:int(x), input().split())) for _ in range(n)]\
)
b=sorted([list(map(lambda x:int(x), input().split())) for _ in range(n)]\
)
rp=n-1
bp=n-1
count=0
for y in reversed(b):
    for x in reversed(r):
	if comp(x, y):
            count+=1
            r.remove(x)
print(count)

Submission status: Runtime Error

Solution code:
■標準入力ショートカット


def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])


import heapq


def solve():
    N = get_next_int()
    red_heap = []
    for i in range(N):
        a, b = get_next_ints()
        heapq.heappush(red_heap, (b, a))
    blue_heap = []
    for i in range(N):
        c, d = get_next_ints()
        heapq.heappush(blue_heap, (d, c))

    blue_heap = sorted(blue_heap)
    red_heap = sorted(red_heap)
    ans = 0
    while(len(blue_heap) > 0):
        blue_pos = heapq.heappop(blue_heap)
        for i in range(len(red_heap)):
            red_pos = red_heap[i]
            if blue_pos[0] > red_pos[0] and blue_pos[1] > red_pos[1]:
                ans += 1
                del red_heap[i]
                break
            elif blue_pos[0] < red_pos[0]:
                break
    print(ans)


solve()

Submission status: Runtime Error

Solution code:
#1. input
n = int(input())
red_list = []
blue_list = []

for i in range(n):
    x, y = map(int, input().split())
    red_list.append([x, y])
for i in range(n):
    x, y = map(int, input().split())
    blue_list.append([x, y])

#2. search
#2.1 red:descending order in y
red_list.sort(key=lambda x:(x[1], x[0]), reverse=True)

#2.2 blue: ascending order
blue_list.sort(key=lambda x:(x[1], x[0]), reverse=False)

#2.3 search a blue point such as [x_r, y_r] < [x_b, y_b]
ans = 0
for red in red_list:
    for blue in blue_list:
        if (red[0]<blue[0]) and (red[1]<blue[1]):
            blue_list.remove(blue)
            ans += 1
            break


#3. print the result
print(ans)
logger.log(30, ans)

Submission status: Runtime Error

Solution code:
def function(count, element):
    for i in range(count):
        element.append(input().split())
        
        
count = int(input())

red = []
blue = []
count_combi = 0
check = [0 for i in range(count)]

function(count, red)
function(count, blue)

for i in range(len(red)):
    if red[i][0] < 0:
        red[i][0] *= -1
    if red[i][1] < 0:
        red[i][1] *= -1

    if blue[i][0] < 0:
        blue[i][0] *= -1
    if blue[i][1] < 0:
        blue[i][1] *= -1
        
red.reverse()
blue.reverse()

for i in range(len(blue)):
    for l in range(len(red)):
        if int(blue[i][0]) >= int(red[l][0]) and int(blue[i][1]) >= int(red[l][1]) and check[l] == 0:
            check[l] = 1
            count_combi += 1
            break

print(count_combi)

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <algorithm>
using namespace std;
struct me{
    int x,y;
}a[105],b[105];
bool f[105];
bool cmp1(struct me v1,struct me v2){
    return v1.y>v2.y;
}
bool cmp2(struct me v1,struct me v2){
    return v1.x+v1.y<v2.x+v2.y;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&b[i].x,&b[i].y);
    //sort(a+1, a+1+n, cmp1);
    sort(b+1, b+1+n, cmp2);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[j]==false&&a[j].x<b[i].x&&a[j].y<b[i].y){
                f[j]=true;
                break;
            }
        }
    }
    int s=0;
    for(int i=1;i<=n;i++)
        if(f[i]==true)
            s++;
    printf("%d\n",s);
    return 0;
}

Submission status: Runtime Error

Solution code:
N = int(input())

red_points = [[int(i) for i in input().split()] for j in range(N)]

blue_points = [[int(i) for i in input().split()] for j in range(N)]

red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    for red_point in red_points:
        if (blue_point[0] > red_point[0]) and (blue_point[1] > red_point[1]):
            if blue_point[1] - red_point[1] < distance:
                distance = blue_point[1] - red_point[1]
                tmp = red_point
    if tmp in red_points:
        red_points.remove(tmp)
        tmp.clear()
        count = count + 1
    distance = 9999
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())

red_points = [[int(i) for i in input().split()] for j in range(N)]

blue_points = [[int(i) for i in input().split()] for j in range(N)]

red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    for red_point in red_points:
        if blue_point[0] > red_point[0]:
            if blue_point[1] > red_point[1]:
                if blue_point[1] - red_point[1] < distance:
                    distance = blue_point[1] - red_point[1]
                    tmp = red_point
        else:
            distance = 9999
            break
    if tmp in red_points:
        red_points.remove(tmp)
        count = count + 1
    distance = 9999
print(count)

Submission status: Runtime Error

Solution code:
red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    for red_point in red_points:
        if blue_point[0] > red_point[0]:
            if blue_point[1] > red_point[1]:
                if blue_point[1] - red_point[1] < distance:
                    distance = blue_point[1] - red_point[1]
                    tmp = red_point
        else:
            distance = 9999
            break
    print(tmp, blue_point)
    print(red_points)
    if tmp in red_points:
        red_points.remove(tmp)
        count = count + 1
    distance = 9999
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
a = 0
x = []
y = []

for i in range(N):
    s,t = map(int, input().split())
    x.append([s,t])

for j in range(N):
    u,v = map(int, input().split())
    y.append([v,u])

x.reverse()
y.sort()

while k < N:
    for l in range(len(x)):
        if x[l][0]<y[k][1] and x[l][1]<y[k][0]:
            a += 1
            del(x[l])
            break
    N += 1

print(a)

Submission status: Runtime Error

Solution code:
# encoding=utf8

n = int(input())

reds = []
for i in range(n):
    reds += [[int(r) for r in input().split(' ')]]

blues = []
for i in range(n):
    blues += [[int(r) for r in input().split(' ')]]

reds = sorted(reds)
blues = sorted(blues)

cnt = 0
for b in blues:
    for r in reds:
        if (r[0] < b[0]) & (r[1] < b[1]):
            cnt += 1
            reds.remove(r)
            blues.remove(b)

print(cnt)

Submission status: Runtime Error

Solution code:
#http://nobuta05.hatenablog.com/entry/2015/11/12/013938
"""
==================================================
二部グラフの最大マッチングを求めるプログラム

# 条件
G = (U,V,E) |U| = |E|

# 入力
U --> 1 2 3 4 .... 10
V --> a b c d .... j
E -->
1 a
1 d
2 b
2 f
etc...

# 出力(最大マッチングの一例)
edges = [(1,a), (2,b), (3 h), ...]

# 定義
def get_edge(M, u, U)    枝集合Mに含まれる枝のうち、頂点uと接している枝の他方の頂点_(1)を返す関数。そのような枝
                         が複数ある場合、一番最初に見つかった頂点を返す。また、引数にUが指定されている場合、(1)
                         を満たし、かつUに含まれる頂点を返す。

def get_nodes(M)         枝集合Mに含まれる枝に関して、左接続の頂点と右接続の頂点に分け、左接続の頂点集合と右接続
                         の頂点集合の二つを返す関数。

def augpath(Si, Ti, M, E)
                         二部グラフにおいて、増大道があるかどうかを判定・処理するプログラム。

==================================================
"""

def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None

def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M

#今回の問題分---------------------------------------------------------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
s.sort(key=lambda x:(x[0],x[1]))
ss.sort(key=lambda x:(x[0],x[1]))
#print(s,ss)

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
pair.sort(key=lambda x:len(x))

#---------------------------------------------------------------------

E = []
U0 = [x for x in range(len(pair))]
V0 = [x for x in range(n)]


for i in range(len(pair)):
    try:
        for j in range(len(pair[i])):
            node1, node2 = i,pair[i][j]
            E.append((node1, node2))
    except:
        pass

# CALC
try:
    edges = Hungary(U0, V0, E)
except:
    pass

# OUTPUT
try:
    print(len(edges))
else:
    print(0)

Submission status: Runtime Error

Solution code:
# encoding=utf8

n = int(input())

reds = []
for i in range(n):
  reds += [[int(r) for r in input().split(' ')]]

blues = []
for i in range(n):
  blues += [[int(r) for r in input().split(' ')]]

cnt = 0
def chk(r, b):
  if (r[0] < b[0]) & (r[1] < b[1]):
    return 1
  else:
    return 0

for b in blues:
  for r in reds:
    buf = chk(r, b)
    if buf > 0:
      cnt += 1
      reds.remove(r)
      blues.remove(b)

print(cnt)

Submission status: Runtime Error

Solution code:
#http://nobuta05.hatenablog.com/entry/2015/11/12/013938
"""
==================================================
二部グラフの最大マッチングを求めるプログラム

# 条件
G = (U,V,E) |U| = |E|

# 入力
U --> 1 2 3 4 .... 10
V --> a b c d .... j
E -->
1 a
1 d
2 b
2 f
etc...

# 出力(最大マッチングの一例)
edges = [(1,a), (2,b), (3 h), ...]

# 定義
def get_edge(M, u, U)    枝集合Mに含まれる枝のうち、頂点uと接している枝の他方の頂点_(1)を返す関数。そのような枝
                         が複数ある場合、一番最初に見つかった頂点を返す。また、引数にUが指定されている場合、(1)
                         を満たし、かつUに含まれる頂点を返す。

def get_nodes(M)         枝集合Mに含まれる枝に関して、左接続の頂点と右接続の頂点に分け、左接続の頂点集合と右接続
                         の頂点集合の二つを返す関数。

def augpath(Si, Ti, M, E)
                         二部グラフにおいて、増大道があるかどうかを判定・処理するプログラム。

==================================================
"""

def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None

def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M

#今回の問題分---------------------------------------------------------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
s.sort(key=lambda x:(x[0],x[1]))
ss.sort(key=lambda x:(x[0],x[1]))
#print(s,ss)

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
pair.sort(key=lambda x:len(x))

#---------------------------------------------------------------------

E = []
U0 = [x for x in range(len(pair))]
V0 = [x for x in range(n)]


for i in range(len(pair)):
    try:
        for j in range(len(pair[i])):
            node1, node2 = i,pair[i][j]
            E.append((node1, node2))
    except:
        pass

# CALC
edges = Hungary(U0, V0, E)

# OUTPUT
print(len(edges))

Submission status: Runtime Error

Solution code:
N=input()
a=[]
for i in range(2*N):
	x,y=map(int, raw_input().split())
	if i<N: a.append([x,y,"R"])
	else: a.append([x,y,"B"])

b=sorted(a, key=lambda x: x[0], reverse=True)


q=[]
ans=0
for i in b:
	x=i[1]
	type=i[2]
	if type=="B":
		q.append(x)
	elif type=="R" and len(q)>0:
		up=0
		tmp=[]
		for j in q:
			if x<=j:
				tmp.append(j)
				up=1
		else:
			ans+=up
		val=min(tmp)
		q.remove(val)

print ans

Submission status: Runtime Error

Solution code:
#http://nobuta05.hatenablog.com/entry/2015/11/12/013938
"""
==================================================
二部グラフの最大マッチングを求めるプログラム

# 条件
G = (U,V,E) |U| = |E|

# 入力
U --> 1 2 3 4 .... 10
V --> a b c d .... j
E -->
1 a
1 d
2 b
2 f
etc...

# 出力(最大マッチングの一例)
edges = [(1,a), (2,b), (3 h), ...]

# 定義
def get_edge(M, u, U)    枝集合Mに含まれる枝のうち、頂点uと接している枝の他方の頂点_(1)を返す関数。そのような枝
                         が複数ある場合、一番最初に見つかった頂点を返す。また、引数にUが指定されている場合、(1)
                         を満たし、かつUに含まれる頂点を返す。

def get_nodes(M)         枝集合Mに含まれる枝に関して、左接続の頂点と右接続の頂点に分け、左接続の頂点集合と右接続
                         の頂点集合の二つを返す関数。

def augpath(Si, Ti, M, E)
                         二部グラフにおいて、増大道があるかどうかを判定・処理するプログラム。

==================================================
"""

def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None

def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M

#今回の問題分---------------------------------------------------------------------

n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
s.sort(key=lambda x:(x[0],x[1]))
ss.sort(key=lambda x:(x[0],x[1]))
#print(s,ss)

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
pair.sort(key=lambda x:len(x))

#---------------------------------------------------------------------

E = []
U0 = [x for x in range(len(pair))]
V0 = [x for x in range(n)]

try:
    for i in range(len(pair)):
        for j in range(len(pair[i])):
            node1, node2 = i,pair[i][j]
            E.append((node1, node2))
except:
    pass

# CALC

edges = Hungary(U0, V0, E)

# OUTPUT
#print('MAX MATCHING ... {0}'.format(len(edges)))

print(len(edges))

Submission status: Runtime Error

Solution code:
N = int(input())
reds = []
for i in range(N):
    reds.append(tuple(map(int, input().split(" "))))
blues = []
for i in range(N):
    blues.append(tuple(map(int, input().split(" "))))
reds.sort(key=lambda x: x.reverse(), reverse=True)
blues.sort()
picked = [False for _ in range(N)]
ans = 0
for blue in blues:
    for i, red in enumerate(reds):
        if blue[0] > red[0] and blue[1] > red[1] and not picked:
            ans += 1
            picked[i] = True
            break
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
ss=[]
for i in range(n):
    s.append([int(i) for i in input().split()])
for i in range(n):
    ss.append([int(i) for i in input().split()])
s.sort(key=lambda x:(x[0],x[1]))
ss.sort(key=lambda x:(x[0],x[1]))
#print(s,ss)

pair=[]
for i in range(len(s)):
    right=[]
    for j in range(n):    
        if s[j][0]<ss[i][0] and s[j][1]<ss[i][1]:
            right.append(j)
    pair.append(right)
pair.sort(key=lambda x:len(x))

#http://nobuta05.hatenablog.com/entry/2015/11/12/013938
"""
==================================================
二部グラフの最大マッチングを求めるプログラム

# 条件
G = (U,V,E) |U| = |E|

# 入力
U --> 1 2 3 4 .... 10
V --> a b c d .... j
E -->
1 a
1 d
2 b
2 f
etc...

# 出力(最大マッチングの一例)
edges = [(1,a), (2,b), (3 h), ...]

# 定義
def get_edge(M, u, U)    枝集合Mに含まれる枝のうち、頂点uと接している枝の他方の頂点_(1)を返す関数。そのような枝
                         が複数ある場合、一番最初に見つかった頂点を返す。また、引数にUが指定されている場合、(1)
                         を満たし、かつUに含まれる頂点を返す。

def get_nodes(M)         枝集合Mに含まれる枝に関して、左接続の頂点と右接続の頂点に分け、左接続の頂点集合と右接続
                         の頂点集合の二つを返す関数。

def augpath(Si, Ti, M, E)
                         二部グラフにおいて、増大道があるかどうかを判定・処理するプログラム。

==================================================
"""

def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None

def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)
    
    

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M



E = []
U0 = [x for x in range(len(pair))]
V0 = [x for x in range(n)]

for i in range(len(pair)):
    for j in range(len(pair[i])):
        node1, node2 = i,pair[i][j]
        E.append((node1, node2))

# CALC

edges = Hungary(U0, V0, E)

# OUTPUT
#print('MAX MATCHING ... {0}'.format(len(edges)))

print(len(edges))

Submission status: Runtime Error

Solution code:
from pprint import pprint

def solve(datas):
    ans = 0
    reds = set()
    for p in datas:
        # pprint(reds)
        if p[0] == "r":
            reds.add(p)
        else:
            if len(reds) != 0:
                partner = max(filter(lambda x: x[1][1] < p[1][1], reds), key=lambda x: x[1][1])
                # pprint(filter(lambda x: x[1][1] < p[1][1], reds))
                reds.remove(partner)
                ans += 1
    return ans

if __name__ == '__main__':
    N = int(input())
    datas = []
    for i in range(N):
        a,b = list(map(lambda x: int(x), input().split(" ")))
        datas.append(("r", (a,b)))
    for i in range(N):
        c,d = list(map(lambda x: int(x), input().split(" ")))
        datas.append(("b", (c,d)))
    # pprint(datas)
    datas.sort(key=lambda x: x[1][0]) # x座標で昇順にソート
    ans = solve(datas)
    print(ans)

Submission status: Runtime Error

Solution code:
# -- coding: utf-8 --
from collections import deque
N = int(input())
red = []
for i in range(N):
    red.append(list(map(int, input().split(' '))))
blue = []
for i in range(N):
    blue.append(list(map(int, input().split(' '))))
red.sorted()
blue.sorted()
red = deque(red)
blue = deque(blue)
count = 0
flag = [0] * N
for b in blue:
    for i, r in enumerate(red):
        if r[0] < b[0] and r[1] < b[1] and flag[i] == 0:
            count += 1
            flag[i] = 1

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
b = []
c = []
d = []
for i in range(0,2n):
    a.append(str(input()).split())

for i in range(0,n):
    d.append(0)

for  i in range(0,n):
    for j in range(n,2n):
        if int(a[i][0]) < int(a[j][0]) and int(a[i][1]) < int(a[j]):
            b.append(1)
        else:
            b.append(0)
        if i == n-1:
            c.append(b)

sum = []
for I in range(0,n+1):
        sum.append(0)
answer = 0
    

for i in range(0,n):
    for j in range(0,n):
        if c[i][j] == 1:
            d[j] = 1
        if j == n-1:
            for k in range(0,n):
                sum[i+1] += d[k]
            if sum[i] >= sum[i-1]:
                answer += 1

print(answer)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

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

red_1 = sorted(red)
blue_1 = sorted(blue)
ans_1 = 0

for i in red_1:
    for j in blue_1:
        if i[0] < j[0] and i[1] < j[1]:
            ans_1 += 1
            blue_1.remove(j)
            break

red.sort()
blue.sort()
red_2 = sorted(red, key=lambda x:sum(x))
blue_2 = sorted(blue, key=lambda x:sum(x))
ans_2 = 0

for i in red_2:
    for j in blue_2:
        if i[0] < j[0] and i[1] < j[1]:
            ans_2 += 1
            blue_2.remove(j)
            break
red_3 = sorted(red, key=lambda x:x[1])
blue_3 = sorted(red, key=lambda x:x[1])
red_3 = sorted(red_3, key=lambda x:sum(x))
blue_3 = sorted(blue_3, key=lambda x:sum(x))
ans_4
for i in red_3:
    for j in blue_3:
        if i[0] < j[0] and i[1] < j[1]:
            ans_4 += 1
            blue_3.remove(j)
            break

from operator import itemgetter
red.sort(key=itemgetter(1))
blue.sort(key=itemgetter(1))
ans_3 = 0

for i in red:
    for j in blue:
        if i[0] < j[0] and i[1] < j[1]:
            ans_3 += 1
            blue.remove(j)
            break

ans = []
ans.append(ans_1)
ans.append(ans_2)
ans.append(ans_3)
ans.append(ans_4)
print(max(ans))

Submission status: Runtime Error

Solution code:
import itertools
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(list(map(int,input().split())))
for j in range(n):
    blue.append(list(map(int,input().split())))
perm=list(itertools.permutations(blue))
pair=0
ans=0
for k in perm:
    for m in range(n):
        if n-m+pair+1<=ans:
            next(m)
        if int(red[m][0])<int(k[m][0]) and int(red[m][1])<int(k[m][1]):
            pair+=1
        
    if pair>ans:
        ans=pair
    if ans==n:
        break
    pair=0
print(ans)