Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All input values are integers.

1 \leq N \leq 100

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum number of friendly pairs.

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

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

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



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


Sample output:
2

Submission status: Accepted

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

for i in range(N):
    B[i] = list(map(int,input().split(" ")))
    
R = sorted(R,key=lambda x:x[1],reverse=True)
B = sorted(B,key=lambda x:x[0])

for b in B:
    for i in range(N):
        r = R[i]
        if not(L[i]) and r[0] < b[0] and r[1] < b[1]:
            L[i] = 1
            break

print(sum(L))

Submission status: Accepted

Solution code:
#ABC091-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n=I()
R=[]
B=[]
for i in range(n):
    x,y=IL()
    R.append([x,y,x+y])
for i in range(n):
    x,y=IL()
    B.append([x,y,x+y])
R.sort(key=lambda x:-x[1])
B.sort(key=lambda x:x[0])
Rb=[True]*n
Bb=[True]*n

ans=0
for i in range(n):
    bx,by,bz=B[i]
    for j in range(n):
        rx,ry,rz=R[j]
        if rx<bx and ry<by and Rb[j] and Bb[i]:
            ans+=1
            Rb[j]=False
            Bb[i]=False
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[0])
cd.sort(key = lambda x:x[0])
cnt = 0
for i in range(N):
    x = cd[i][0]
    tmplist = []
    for j in range(len(ab)):
        if ab[j][0] >= x:
            break
        tmplist += [ab[j]]
    tmplist.sort(key = lambda x:x[1],reverse = True)
    for j in range(len(tmplist)):
        if cd[i][1] > tmplist[j][1]:
            cnt += 1
            ab.remove(tmplist[j])
            break
        
print(cnt)

Submission status: Accepted

Solution code:
def main():
    num = int(input())
    aka_data = [list(map(int, input().split())) for i in range(num)]
    ao_data = [list(map(int, input().split())) for i in range(num)]

    aka_data.sort(key=lambda x:-x[1])
    ao_data.sort(key=lambda x: x[0])

    ans = 0
    for j in range(num):
        for i in range(len(aka_data)):
            if aka_data[i][0] < ao_data[j][0] and aka_data[i][1] < ao_data[j][1]:
                aka_data.pop(i)
                ans += 1
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
red = [list(map(int, input().split())) for i in range(n)]
red = sorted(red, reverse=True)
blue = [list(map(int, input().split())) for i in range(n)]
blue = sorted(blue, key=lambda x: x[1])
ans = 0
for re in red:
    a, b = re
    for i, bu in enumerate(blue):
        c, d = bu
        if a < c and b < d:
            ans += 1
            blue.pop(i)
            break
print(ans)

Submission status: Accepted

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

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


def func():
    global A_sorted, B_sorted
    count = 0
    for b in B_sorted:
        a = None
        A_sorted_cp = A_sorted[:]
        while True:
            if len(A_sorted_cp) == 0:
                break
            a = A_sorted_cp.pop(0)
            if a[0] < b[0] and a[1]<b[1]:
                count += 1
                A_sorted.pop(A_sorted.index(a))
                break
    return count
            
    

print(func())

Submission status: Accepted

Solution code:
# 問題 https://atcoder.jp/contests/abc091/tasks/arc092_a
# 素晴らしくわかりやすい解説 https://speakerdeck.com/ichijyo/atcoder-beginner-contest-091-c-2d-plane-2n-points-fei-gong-shi-jie-shuo
# 別の解説　https://pitsbuffersolution.com/compro/atcoder/arc092c.php

# 解説が豊富な実装 https://atcoder.jp/contests/abc091/submissions/5250954

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

# 青い点を基準に組み合わせの赤い点を探したい

# 赤い点も青い点もx座標をもとに並び替えたい
AB.sort()
CD.sort()

from operator import itemgetter


# 青い点について小さい順にマッチングさせていく
cnt = 0
for c, d in CD:
    # c,dよりも小さい中で一番大きいy座標が大きいものを選ぶ
    del_idx = None
    tmpmax = -1
    for i, (a, b) in enumerate(AB):
        if a < c and b < d:
            if b > tmpmax:
                # print('cd=({},{})'.format(c, d))
                # print('red=({},{})'.format(a, b))
                tmpmax = b
                del_idx = i

    if del_idx is not None:
        # print(del_idx)
        AB[del_idx] = [float('inf'), float('inf')]
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc091/tasks/arc092_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    N = int(input())
    red = [list(map(int, input().split())) for _ in range(N)]
    red.sort(key=lambda x: x[0])

    blue = [list(map(int, input().split())) for _ in range(N)]
    blue.sort(key=lambda x: x[0])

    ans = 0
    for bx, by in blue:
        p_red = None
        for i in range(len(red)):
            rx, ry = red[i][0], red[i][1]
            if rx > bx:
                break
            if ry < by:
                if not p_red:
                    p_red = red[i]
                else:
                    if p_red[1] < ry:
                        p_red = red[i]
        if p_red:
            ans += 1
            red.remove(p_red)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

    reddots = [list(map(int, input().split())) for _ in range(N)]
    bluedots = [tuple(map(int, input().split())) for _ in range(N)]

    reddots = sorted(reddots, key=lambda x: x[1], reverse=True)
    bluedots = sorted(bluedots, key=lambda x: x[0])

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

    reddots = [list(map(int, input().split())) for _ in range(N)]
    bluedots = [tuple(map(int, input().split())) for _ in range(N)]

    reddots = sorted(reddots, key=lambda x: x[1], reverse=True)
    bluedots = sorted(bluedots, key=lambda x: x[0])

    ans = 0
    for blue in bluedots:
        for red in reddots:
            if red[0] < blue[0] and red[1] < blue[1]:
                ans += 1
                red[0] = 201
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#入力
N = int(input())

#赤の座標を取得-->並び替えて左ほど小さくする
red = []
for i in range(N):
    a = list(map(int, input().split()))
    red += [a]
red.sort(reverse = False)

#青の座標を取得-->並び替えて左ほど小さくする
blue = []
for i in range(N):
    a = list(map(int, input().split()))
    blue += [a]
blue.sort(reverse = False)

#blue[m]がペアを作れるかどうかをTrue or Falseで返す
def judge(m): 
    INF = 10 ** 9
    count = 0
    memo = -1
    for i in range(N): #redのリストを小さい順に探索
        if blue[m][0] > red[i][0]: #x座標が条件を満たすか確認       
            #条件を満たす中で最大のy座標を探す
            if memo < red[i][1] and blue[m][1] > red[i][1]: 
            #red[i][1]=赤のy座標が最も大きくかつ、blue[m][1]=青のy座標より小さい時    
                count = 1 #1つでも条件を満たすものがあれば、count = 1にする
                memo = max(memo, red[i][1]) #最も大きいy座標を記録
                memo_i = i #最も大きくなるときのiをメモ
    if count == 0: #iのループを回してもカウントが増えない=x座標が条件を満たすことが一度もない
        return False
    else: #少なくとも一回は条件を満たした。
        red[memo_i][0] = INF #使ったものをINFで書き換え
        red[memo_i][1] = INF #使ったものをINFで書き換え
        return True

count = 0
for s in range(N): #blue内のxが最も小さいののから着目
    if judge(s):
        count += 1
print (count)

Submission status: Accepted

Solution code:
#入力
N = int(input())

red_x = []
red_y = []
for i in range(N):
    a = list(map(int, input().split()))
    red_x += [a]
    red_y += [a[::-1]]
red_x.sort(reverse = False)
red_y.sort(reverse = False)
#print (red_x, red_y)


blue_x = []
blue_y = []

for i in range(N):
    a = list(map(int, input().split()))
    blue_x += [a]
    blue_y += [a[::-1]]
blue_x.sort(reverse = False)
blue_y.sort(reverse = False)
#print (blue_x, blue_y)

def judge_x(m): #blue[m]がペアを作れるかどうかをTrue or Falseで返す x優先
    INF = 10 ** 9
    count = 0
    memo = -1
    for i in range(N):
        if blue_x[m][0] > red_x[i][0]: #x座標が条件を満たすか確認
            
            #条件を満たす中で最大のy座標を探す

            #y座標の確認をしてない！！！！ｓ
            #
            if memo < red_x[i][1] and blue_x[m][1] > red_x[i][1]: 
                count = 1
                memo = max(memo, red_x[i][1]) #最も大きいy座標を記録
                memo_i = i
    if count == 0: #iのループを回してもカウントが増えない=x座標が条件を満たすことが一度もない
        return False
    else: #少なくとも一回は条件を満たした。
        red_x[memo_i][0] = INF #使ったものをINFで書き換え
        red_x[memo_i][1] = INF #使ったものをINFで書き換え
#        print (red_x)
        return True
    return False

def judge_y(m): #blue[m]がペアを作れるかどうかをTrue or Falseで返す y優先
    INF = 10 ** 9
    for i in range(N):
        if blue_y[m][1] > red_y[i][1]:
            if blue_y[m][0] > red_y[i][0]:
                red_y[i][1] = INF
                return True
        else:
            pass
    return False

count_x = 0
for s in range(N): #blue内のxが最も小さいののから着目
    if judge_x(s):
        count_x += 1
print (count_x)

#count_y = 0    
#for t in range(N):
#    if judge_y(t):
#        count_y += 1
#print (count_y)

#print (max(count_x, count_y))
#print (judge(0))
#print (judge(1))
#print (judge(2))
#print (judge(3))
#print (judge(4))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
reds = list()
blues = list()
counter = 0

for i in range(n):
    reds.append(list(map(int,input().split())))
    
for i in range(n):
    blues.append(list(map(int,input().split())))
    
blues = sorted(blues,key=lambda x:x[0])
reds = sorted(reds,key=lambda x:x[1],reverse=True)

for blue in blues:
    for red in reds:
        if red[0] < blue[0] and red[1] < blue[1]:
            red[1] = 201
            counter += 1
            break
print(counter)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_edge(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    red = [[a[i], b[i]] for i in range(N)]
    blue = [[c[i], d[i]] for i in range(N)]

    # 最大マッチング問題として解く。
    dn = Dinic(2*N+2)
    for i, (rx, ry) in enumerate(red):
        dn.add_edge(0, i+1, 1)
    for j, (bx, by) in enumerate(blue):
        dn.add_edge(N+j+1, 2*N+1, 1)

    for i, (rx, ry) in enumerate(red):
        for j, (bx, by) in enumerate(blue):
            if rx < bx and ry < by:
                dn.add_edge(i+1, N+j+1, 1)

    ans = dn.max_flow(0, 2*N+1)
    print(ans)

    # print(dn.links)


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:
def main():
	N = int(input())
	red = [[0, 0] for _ in range(N)]
	blue = [[0, 0] for _ in range(N)]
	for i in range(N):
		red[i] = list(map(int, input().split()))
	for i in range(N):
		blue[i] = list(map(int, input().split()))

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

	ans = 0
	for b in blue:
		removes = []
		for i, r in enumerate(red):
			if r[0] < b[0] and r[1] < b[1]:
				removes.append([r[1], i])
		if len(removes) > 0:
			removes.sort(key=lambda x: -x[0])
			ans += 1
			red.pop(removes[0][1])

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
# import matplotlib.pyplot as plt


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    red = [[a[i], b[i], False] for i in range(N)]
    blue = [[c[i], d[i], False] for i in range(N)]

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

    # print(red)
    # print(blue)
    ans = 0

    for b in blue:
        cand = [i for i, r in enumerate(red) if r[0] < b[0] and r[1] < b[1]]
        # fix
        if len(cand) > 0:
            ans += 1
            i = max(cand, key=lambda i: red[i][1])
            red.pop(i)
    print(ans)

    # flag = True
    # while flag:
    #     flag = False
    #     for i in range(N):
    #         if red[i][2] == True:
    #             continue
    #         cand = []
    #         counter = 0
    #         for j in range(N):
    #             if blue[j][2] == True:
    #                 continue
    #             if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
    #                 counter += 1
    #                 cand.append(j)
    #         if counter == 1:
    #             red[i][2] = True
    #             blue[cand[0]][2] = True
    #             flag = True
    #             ans += 1
    #             print("pair ", red[cand[0]], blue[cand[0]])
    # print(ans)
    # for i in range(N):
    #     if red[i][2]:
    #         plt.scatter(red[i][0], red[i][1], color="red", marker="o")
    #     else:
    #         plt.scatter(red[i][0], red[i][1], color="orange", marker="o")
    # for i in range(N):
    #     if blue[i][2]:
    #         plt.scatter(blue[i][0], blue[i][1], color="blue", marker="o")
    #     else:
    #         plt.scatter(blue[i][0], blue[i][1], color="navy", marker="o")
    # plt.show()
    # return


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:
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])
ans = 0
for i in range(N):
  maxy=-1
  maxyidx=0
  for j in range(N):
    if blue[i][0]>red[j][0] and blue[i][1]>red[j][1] and red[j][1]>maxy:
      maxy = red[j][1]
      maxyidx = j
  if maxy>-1:
    ans += 1
    red[maxyidx][1]=-1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(i) for i in input().split(" ")] for _ in range(N)]
cd = [[int(i) for i in input().split(" ")] for _ in range(N)]
ab_sort = sorted(ab, key=lambda x:-x[1])
cd_sort = sorted(cd, key=lambda x:x[0])

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

print(cnt)

Submission status: Accepted

Solution code:
length = int(input())
lower = []
higher = []
for i in range(length):
    x, y = map(int, input().split(" "))
    lower.append([x, y])

for i in range(length):
    x, y = map(int, input().split(" "))
    higher.append([x, y])

match = [set() for n in range(length)]
for high in range(length):
    for low in range(length):
        high_x, high_y = higher[high][0], higher[high][1]
        low_x, low_y = lower[low][0], lower[low][1]
        if high_x > low_x and high_y > low_y:
            match[high] |= {low}

matched_lower_set = set()
matched_higher_set = set()

def ret_minimum_match(match, lower_i, matched_higher_set, matched_lower_set):
    min_i = -1
    min_len = 101
    for i, ma in enumerate(match):
        if i in matched_higher_set or lower_i not in ma:
            continue
        if min_len > len(ma - matched_lower_set) > 0:
            min_len = len(ma - matched_lower_set)
            min_i = i
    return {min_i}

while True:

    lowers = [[] for n in range(length)]
    for i, mat in enumerate(match):
        if i in matched_higher_set:
            continue
        for m in mat:
            if m not in matched_lower_set:
                lowers[m].append(i)
    only_one_deleted = 0
    # print(lowers, matched_lower_set, matched_higher_set)
    for i, lo in enumerate(lowers):
        if len(lo) == 1:
            matched_higher_set |= ret_minimum_match(match, i, matched_higher_set, matched_lower_set)
            matched_lower_set |= {i}
            only_one_deleted = 1
            break

    if all([True if len(n) <= 0 else False for n in lowers]):
        break
    if not only_one_deleted:
        min_i, min_len = -1, 101
        for i, lo in enumerate(lowers):
            if min_len > len(lo) > 0:
                min_i = i
                min_len = len(lo)
        matched_higher_set |= ret_minimum_match(match, min_i, matched_higher_set, matched_lower_set)
        matched_lower_set |= {min_i}

print(len(matched_lower_set))

Submission status: Accepted

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

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

for i in range(N):
    for j in range(N):
        if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1]:
            count += 1
            ab[j] = [200, 200]
            break
        
print(count)

Submission status: Accepted

Solution code:
n = int(input())

red = []
blue = []


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


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

ans = 0

for i in red.copy():
  for j in blue.copy():
    p,q = i
    r,s = j
    if p < r and q < s:
      ans += 1
      red.remove([p, q])
      blue.remove([r, s])
      break
      
print(ans)

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

#############################################

N = int(input())
reds = [ l_inpl() for _ in range(N)]
blues = [ l_inpl() for _ in range(N)]

reds.sort(key=lambda a:a[1], reverse=True)
blues.sort()


ans = 0
for b_ind in range(N):
    bx, by = blues[b_ind][0], blues[b_ind][1]
    for r_ind in range(len(reds)):
        rx, ry = reds[r_ind][0], reds[r_ind][1]
        if rx < bx and ry < by:
            reds.remove([rx, ry])
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a,b,c,d,red,blue=[],[],[],[],[],[]
for i in range(N):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
for i in range(N):
    ci,di=list(map(int,input().split()))
    c.append(ci)
    d.append(di)
for i in range(N):
    red.append([a[i],b[i]])
    blue.append([c[i],d[i]])

cxy = []
for i in range(N):
    cxy.append(["r",red[i][0],red[i][1],0])
    cxy.append(["b",blue[i][0],blue[i][1],0])

cxy_sort = sorted(cxy, key=lambda x: x[1])

cnt=0
for i in range(N*2):
    counter = -1
    max=0
    for j in range(0,i):
        if cxy_sort[i][0] == "b" and cxy_sort[j][0] == "r" and cxy_sort[j][3] == 0 and cxy_sort[i][2] - cxy_sort[j][2] >0:
            if cxy_sort[j][2] >= max:
                max = cxy_sort[j][2]
                counter = j
    if counter != -1:
        cxy_sort[counter][3] = 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

R = [()] * N
B = [()] * N

for i in range(N):
    a, b = map(int, input().split())
    R[i] = (a,b)

for i in range(N):
    a, b = map(int, input().split())
    B[i] = (a, b)

B = sorted(B)

ans = 0
for a, b in B:
    d = -1
    mem = -1
    for i in range(len(R)):
        if R[i][0] < a and R[i][1] < b:
            if mem <= R[i][1]:
                d = i
                mem = R[i][1]
    if d != -1:
        R.pop(d)
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
N=int(input())
r=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda q: q[0], reverse=True)
b=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda q: q[1])
ans=0
for rx,ry in r:
	for i in range(len(b)):
		bx,by=b[i]
		if bx>rx and by>ry:
			ans+=1
			b.pop(i)
			break
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
CD = [list(map(int,input().split())) for _ in range(N)]
AB.sort(reverse=1,key=lambda x:x[1])
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:
# 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=int(input())
p=[list(map(int,input().split())) for i in range(N)]
q=[list(map(int,input().split())) for i in range(N)]

work=Dinic(2*N+2)
# S=0,G=2*N+1, p:1--N,q:N+1--2*N

for i in range(1,N+1):
    work.add_edge(0,i,1)
    work.add_edge(N+i,2*N+1,1)

for i in range(N):
    for j in range(N):
        if p[i][0]<q[j][0] and p[i][1]<q[j][1]: work.add_edge(i+1,N+j+1,1)


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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import random
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    red = [LI() for _ in range(n)]
    blue = [LI() for _ in range(n)]
    blue.sort()

    used = [0] * n
    res = 0
    for a, b in blue:
        t = -1
        k = -1
        for i, (x, y) in enumerate(red):
            if used[i]:
                continue

            if x < a and b > y > t:
                t = y
                k = i

        if k != -1:
            used[k] = 1
            res += 1

    return res


print(main())

Submission status: Accepted

Solution code:
n=int(input())
x=sorted([tuple(map(int,input().split()))for i in range(n)],key=lambda x:x[1])[::-1]
y=sorted([tuple(map(int,input().split()))for i in range(n)])
#print(x)
#print(y)
ans=0
for j in x.copy():
    for i in y.copy():
        s,t=i
        p,q=j
        if p<s and q<t:
            y.remove((s,t))
            x.remove((p,q))
            #print(p,q,s,t)
            ans+=1
            break
    #print(x,y)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
for i in range(N):
    x, y = map(int, input().split())
    red.append((x, y))
for i in range(N):
    x, y = map(int, input().split())
    blue.append((x, y))
red.sort(key=lambda x: x[0])
blue.sort(key=lambda x: x[0])
ans = 0
for j in range(N):
    index = -1
    for i in range(len(red)):
        if red[i][0] >= blue[j][0]:
            break
        elif red[i][1] < blue[j][1]:
            if index == -1 or red[index][1] < red[i][1]:
                index = i
    if index != -1:
        red.remove(red[index])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

AB = sorted(AB, key=itemgetter(0), reverse=True)
CD = sorted(CD, key=itemgetter(1))
is_pair = [False for _ in range(N)]

count = 0

for a, b in AB:
    for i, cd in enumerate(CD):
        c, d = cd
        if is_pair[i]:
            continue
        if a < c and b < d:
            is_pair[i] = True
            count += 1
            break

print(count)

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
CD = [list(map(int, input().split())) for i in range(N)]
AB = sorted(AB, key=lambda x: x[1], reverse=True)
CD = sorted(CD)
ans = 0
for cd in CD:
    for ab in AB:
        if cd[0] > ab[0] and cd[1] > ab[1]:
            ans += 1
            AB.remove(ab)
            break


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[1], reverse=True)
CD = sorted([list(map(int, input().split())) for _ in range(N)])
ans = 0
for cd in CD:
    for ab in AB:
        if cd[0] > ab[0] and cd[1] > ab[1]:
            ans += 1
            AB.remove(ab)
            break


print(ans)

Submission status: Accepted

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

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

print(cnt)