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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
red = sorted(LIR(n), key=lambda x:x[1], reverse=True)
blue = sorted(LIR(n))
red_used = [0] * n
for i in range(n):
    blue_x, blue_y = blue[i]
    for j in range(n):
        red_x, red_y = red[j]
        if red_x < blue_x and red_y < blue_y and not red_used[j]:
            red_used[j] = 1
            break


print(sum(red_used))

Submission status: Accepted

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

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

    B.sort(key=lambda x:x[0]) # Bをxでソート
    ans = 0
    while B:
        Bm = []
        for b in B:
            if b[0] == B[0][0]:
                Bm.append(b)
        Bm.sort(key=lambda x:x[1]) # xが最小のbのリストを、yでソート

        while Bm:
            b = Bm[0] # xが最小のbを、yが小さい順に処理
            cr = []
            for r in R:
                if r[0]<=b[0] and r[1]<=b[1]:
                    cr.append(r) # ペア候補
            if cr:
                cr.sort(key=lambda x:x[1]) # 候補のうち、yが最大のもの
                R.remove(cr[-1])
                ans += 1
            Bm.remove(b)
            B.remove(b)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N=int(input())
    R=[]
    for _ in range(N):
        R.append(list(map(int, input().split())))
    B=[]
    for _ in range(N):
        B.append(list(map(int, input().split())))
    B.sort(key=lambda x:x[0]) # 解説の通り。Bをxでソート
    ans = 0
    while B:
        b = B[0] # x が最小の b を順に処理
        cr = []
        for r in R:
            if r[0]<=b[0] and r[1]<=b[1]:
                cr.append(r) # ペア候補
        if cr:
            cr.sort(key=lambda x:x[1]) # 候補のうち、yが最大のもの
            R.remove(cr[-1])
            ans += 1
        B.remove(b)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ABs = []
for i in range(N):
  a, b = map(int, input().split())
  ABs.append((a, b))
CDs = []
for i in range(N):
  c, d = map(int, input().split())
  CDs.append((c, d))
ABs.sort()
CDs.sort()
r = 0
s = set()
for c, d in CDs:
  ma, mb = -1, -1
  for a, b in ABs:
    if a < c and b < d and b > mb and (a, b) not in s:
      ma, mb = a, b
  if not ma < 0:
    r += 1
    s.add((ma, mb))
    #print(ma, mb)
print(r)

Submission status: Accepted

Solution code:
n = int(input())
points = []
for _ in range(n):
    a, b = map(int, input().split())
    points.append((a, b, 'red'))
for _ in range(n):
    c, d = map(int, input().split())
    points.append((c, d, 'blue'))
points.sort()

used = set()
for i in range(len(points)):
    x1, y1, color1 = points[i]
    if color1 == 'red':
        continue
    
    y = -1
    k = -1
    for j in range(0, i):
        x2, y2, color2 = points[j]
        if color2 == 'red' and not j in used and y2 < y1 and abs(y2 - y1) < abs(y - y1):
            y = y2
            k = j
    
    if k != -1:
        used.add(k)

print(len(used))

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)])
cnt = 0
for a, b in ab:
  for c, d in cd:
    if a<c and b<d:
      cd.remove([c,d])
      cnt+=1
      break

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
ls0 = [list(map(int, input().split())) for _ in range(n)]
ls1 = [list(map(int, input().split())) for _ in range(n)]
ls0.sort(key=lambda x: x[0], reverse=True)
count = 0
for x0, y0 in ls0:
    val = float('inf')
    index = -1
    for i, (x1, y1) in enumerate(ls1):
        if x0 <= x1:
            if y0 <= y1 < val:
                index = i
                val = y1
    if index >= 0:
        count += 1
        ls1.remove(ls1[index])
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

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

red_flag = [0] * n
ans = 0
for i in range(n):
    idx = -1
    for j in range(n):
        if red[j][0] >= blue[i][0] or red[j][1] >= blue[i][1] or red_flag[j] == 1:
            continue
        if idx == -1 or red[idx][1] < red[j][1]:
            idx = j

    if idx >= 0:
        red_flag[idx] = 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

Red.sort(key=itemgetter(0), reverse=True)
checked = [False for _ in range(N)]

c = 0
for rx, ry in Red:
    P = []
    for i, (bx, by) in enumerate(Blue):
        if bx > rx and by > ry and not checked[i]:
            P.append((i, by))
    if P:
        P.sort(key=itemgetter(1))
        ip, _ = P[0]
        checked[ip] = True
        c += 1

print(c)

Submission status: Accepted

Solution code:
import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        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())
red = [list(map(int,input().split())) for i in range(N)]
blue = [list(map(int,input().split())) for i in range(N)]


red = sorted(red, key = lambda a: a[1])
red = sorted(red, key = lambda a: a[0])
blue = sorted(blue, key = lambda a: a[1])
blue = sorted(blue, key = lambda a: a[0])

btor = [[] for i in range(N)]

for i in range(N):
    by,bx = blue[i]
    for j in range(N):
        ry,rx = red[j]
        if ry < by and rx < bx:
            btor[i].append(j)

A = Dinic(2*N+2)

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

for i in range(N):
    for j in btor[i]:
        A.add_edge(i+1, N+1+j,1)
        
ans = A.max_flow(0,2*N+1)
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
aka = []
ao = []
for _ in range(n):
    ab = list(map(int, input().split()))
    aka.append(ab)
aka = sorted(aka, key=lambda x:x[1], reverse=True)
for _ in range(n):
    cd = list(map(int, input().split()))
    ao.append(cd)
ao = sorted(ao)
count = 0
for a, b in aka:
    for c, d in ao:
        if a<c and b<d:
            ao.remove([c,d])
            count+=1
            break
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])
r_list = []
b_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    r_list.append((a, b))

blue_dict = {}

for _ in range(N):
    c, d = list(map(int, input().split()))
    b_list.append((c, d))
    blue_dict[(c, d)] = []
    for ab in r_list:
        a, b = ab
        if a < c and b < d:
            blue_dict[(c, d)] += [(a, b)]

    if blue_dict[(c, d)]:
        # y座標が大きい順に並び替え
        blue_dict[(c, d)] = sorted(blue_dict[(c, d)], key=lambda x: x[0], reverse=True)

# x座標が小さい順に並び替え
b_list = sorted(b_list, key=lambda x: x[1])
pair_list = []

for b in b_list:
    kouho_r_list = blue_dict[b]
    if kouho_r_list:
        r = kouho_r_list[0]
        pair_list.append((r, a))

        for k, v in blue_dict.items():
            if r in v:
                v.remove(r)

ans = len(pair_list)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])
r_list = []
b_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    r_list.append((a, b))

blue_dict = {}

for _ in range(N):
    c, d = list(map(int, input().split()))
    b_list.append((c, d))
    blue_dict[(c, d)] = []
    for ab in r_list:
        a, b = ab
        if a < c and b < d:
            blue_dict[(c, d)] += [(a, b)]

b_list = sorted(b_list, key=lambda x: x[1])
pair_list = []

for b in b_list:
    # xが小さいものから見ていく
    kouho_r_list = blue_dict[b]
    if kouho_r_list:
        kouho_r_list = sorted(kouho_r_list, key=lambda x: x[0], reverse=True)
        r = kouho_r_list[0]
        pair_list.append((r, a))

        for k, v in blue_dict.items():
            if r in v:
                v.remove(r)

ans = len(pair_list)
print(ans)

Submission status: Accepted

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

blue.sort()

found=[0]*n
for bx, by in blue:
    y=-1
    pair=-1

    for i,r in enumerate(red):
        rx, ry=r
        if found[i]:
            continue
        if bx>rx and by>ry:
            if ry>y:
                pair=i
                y=ry

    if pair!=-1:
        found[pair]=1

print(sum(found))

Submission status: Accepted

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

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

found=[0]*n
for bx, by in blue:
    y=-1
    pair=-1

    for i,r in enumerate(red):
        rx, ry=r
        if found[i]:
            continue
        if bx>rx and by>ry:
            if ry>y:
                pair=i
                y=ry

    if pair!=-1:
        found[pair]=1

print(sum(found))

Submission status: Accepted

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

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

cnt=0

for a,b in ab:
    flag=False
    for c,d in cd:
        if a<c and b<d:
            cnt+=1
            flag=True
            break
    if flag==True:
        cd.remove((c,d))
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

red = []
blue = []

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

for b in blue:
	max_red_y = -1
	paired = (-1, -1)

	for r in red:
		# se o x de de red for maior que blue, nao faz nada
		if r[0] > b[0]:
			break
		# para red com o y menor que blue e maior que outros red
		# este sera o novo red com maior y
		# e sera o novo par de blue
		if max_red_y < r[1] < b[1]:
			max_red_y = r[1]
			paired = r
	# se houve atualizacao de pontos pareados
	# incrementa o count
	# e remove este ponto do red, para nao ser varrido nos proximos loops
	if paired != (-1, -1):
		red.remove(paired)
		count += 1

print(count)

Submission status: Accepted

Solution code:
#PDF解説
N = int(input())
Red, Blue = [], []
for n in range(N):
  Red.append([int(ab) for ab in input().split()])
Red.sort(key=lambda x: x[1], reverse=True)
for n in range(N):
  Blue.append([int(cd) for cd in input().split()])
Blue.sort(key=lambda x: x[0])

pairs = 0
for B in Blue:
  c, d = B
  for R in Red:
    a, b = R
    if a < c and b < d:
      pairs += 1
      Red.remove(R)
      break

print(pairs)

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(reverse=True)
CD.sort()

res = 0
for a,b in AB:
    tmp = -1
    for i in range(N):
        if CD[i] != -1:
            c,d = CD[i]
            if a < c and b < d:
                if tmp == -1:
                    tmp = i
                else:
                    if CD[tmp][1] > CD[i][1]:
                        tmp = i
    if tmp != -1:
        CD[tmp] = -1
        res += 1
print(res)

Submission status: Accepted

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

def main():
    N = int(input())
    ab = sorted([list(map(int, input().split())) for i in range(N)], reverse=True)
    cd = sorted([list(map(int, input().split())) for i in range(N)])

    check = [False] * N
    ans = 0
    for i in range(N):
        a, b = ab[i]
        min_ = int(1e5)
        ind = -1
        for i in range(N):
            if not check[i]:
                c, d = cd[i]
                if c > a and d > b:
                    if min_ > d:
                        min_ = d
                        ind = i
        if ind != -1:
            check[ind] = True
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

red = []
blue = []

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

for i in range(N):
    c, d = map(int, input().split())
    blue.append((c, d))

ans = 0
for c, d in sorted(blue, key=lambda x: x[0]):
    candidate = sorted([x for x in red if x[0] < c and x[1] < d and x[2]], key=lambda x: -x[1])
    if candidate:
        candidate[0][2] = False
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red_coordinate = []
blue_coordinate = []
for i in range(n):
    a,b = map(int, input().split())
    red_coordinate.append([b,a]) #先y座標
for i in range(n):
    c, d = map(int, input().split())
    blue_coordinate.append([c,d]) #先x座標

red_coordinate.sort(reverse = True) #赤い点の座標はy座標が大きい順に並ぶ
blue_coordinate.sort() #青い点の座標はx座標が小さい順に並ぶ
ans = 0

for i in range(n): #青い点について回す
    for j in range(n): #赤い点について回す
        find = False
        if blue_coordinate[i][0] > red_coordinate[j][1] \
            and blue_coordinate[i][1] > red_coordinate[j][0]:
            ans = ans + 1
            red_coordinate[j][0] = float('inf')
            red_coordinate[j][1] = float('inf')
            find = True
        
        if find:
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
# def ds(L):
#     R = []
#     curr = L[0][0]
#     tmp = [L[0]]
#     for l in L[1::]:
#         if curr == l[0]:
#             tmp.append(l)
#         else:
#             tmp.sort(key=lambda x : x[1])
#             R + tmp
#             curr = l[0]
#             tmp = [l]
#     return R

N =  int(sys.stdin.readline())
A =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
B =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]

A.sort()
B.sort()

cnt = 0
for b in range(N):
    idx = -1
    ty = -1
    for a in range(N):
        # 貪欲法で赤い点(A)のうち最もyが大きいものを見つける
        if A[a][0] < B[b][0] and A[a][1] < B[b][1]:
            if ty < A[a][1]:
                idx = a
                ty = A[a][1]
    # 見つかった場所は使用不可能にする
    if ty > -1:
        A[idx][0] = 10 ** 10
        A[idx][1] = 10 ** 10
        cnt += 1

print(cnt)

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)]
used = [False] * n
a.sort(key = lambda x: x[0], reverse = True)
b.sort(key = lambda x: x[0], reverse = True)
result = 0
for i in range(n):
  pj = -1
  miny = float('inf')
  for j in range(n):
    if used[j]:
      continue
    if a[i][0] < b[j][0] and a[i][1] < b[j][1]:
      if b[j][1] < miny:
        pj = j
        miny = b[j][1]
  if pj != -1:
    used[pj] = True
    result += 1
print(result)

Submission status: Accepted

Solution code:
from operator import itemgetter
n=int(input())
r=[list(map(int,input().split())) for i in range(n)]
b=[list(map(int,input().split())) for i in range(n)]
r.sort()
b.sort()
ct=0
for i in range(n):
  x=b[i][0];y=b[i][1]
  L=[]
  for j in range(len(r)):
    if r[j][0]<x and r[j][1]<y:
      L.append(r[j])
    L=sorted(L,key=itemgetter(1))
  if len(L)>0:
    r.remove(L[len(L)-1])
    ct+=1
print(ct)

Submission status: Accepted

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

r_stars.sort()
b_stars.sort()
cnt = 0
r_paired = {}
for bs in b_stars:
  rx = ry = -1
  for rs in r_stars:
    if rs[0] < bs[0] and rs[1] < bs[1] and not rs in r_paired:
      if ry < rs[1]:
        rx, ry = rs[0], rs[1]
  if rx != -1:
    cnt += 1
    r_paired[(rx, ry)] = 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
reds = [list(map(int, input().split())) for _ in range(n)]
blues = [list(map(int, input().split())) for _ in range(n)]
reds = sorted(reds, key=lambda x:x[1])
blues = sorted(blues, key=lambda x:x[0])
used = [0 for _ in range(n)]

for blue in blues:
    possible_x = 0
    possible_y = 0
    possible_i = float('inf')
    for i in range(len(reds)):
        if blue[0] >= reds[i][0] and blue[1] >= reds[i][1] and used[i] == 0:
            if possible_y <= reds[i][1]:
                possible_x = reds[i][0]
                possible_y = reds[i][1]
                possible_i = i
    if possible_i != float('inf'):
        used[possible_i] = 1
    
print(sum(used))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n)]
cd = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))
cd.sort(key = itemgetter(0))
ans = 0
for i in range(n):
    lst = []
    x,y = cd[i]
    for j in range(len(ab)):
        a,b = ab[j]
        if a <= x and b <= y:
            lst.append([a,b])
    if len(lst) == 0:
        continue
    lst.sort(key = itemgetter(1),reverse = True)
    ab.remove(lst[0])
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')
N = int(input())
A = []
B = []
for _ in range(N):
    A.append(tuple(map(int, input().split())))
for _ in range(N):
    B.append(tuple(map(int, input().split())))
B.sort(key=lambda t: t[0])

count = 0
for i in range(N):
    x, y = B[i]
    max_y = -1
    idx = -1
    for j in range(len(A)):
        tx, ty = A[j]
        if x > tx and y > ty:
            if max_y < ty:
                max_y = ty
                idx = j
    if idx >= 0:
        A.pop(idx)
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque

class Dinic:
    def __init__(self, v, inf=10**9+7):
        self.V = v
        self.inf = inf
        self.G = [list() for _ in range(v)]
        self.level = [-1 for _ in range(v)]
        self.iter = [0]*v

    def addedge(self,fr,to,cap):
        """
        G[fr] = [to, cap, rev]
        """
        go = [to, cap, None]
        go[2] = back = [fr, 0, go]
        self.G[fr].append(go)
        self.G[to].append(back)

    def bfs(self,st,en):
        q = deque([st])
        self.level = [-1 for _ in range(self.V)]
        self.level[st] = 0
        while q:
            cur = q.popleft()
            for x,cap,_ in self.G[cur]:
                if cap and self.level[x]<0:
                    self.level[x] = self.level[cur] + 1
                    q.append(x)
        return self.level[en] > 0

    def dfs(self,v,t,f):
        if v == t:
            return f
        for e in self.iter[v]:
            w,cap,rev = e
            if cap and self.level[v]<self.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
        while self.bfs(s,t):
            self.iter = list(map(iter, self.G))
            f = self.dfs(s,t,self.inf)
            while f:
                flow += f
                f = self.dfs(s,t,self.inf)
        return flow
n = int(input())
dinic = Dinic(n*2+2)
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
  dinic.addedge(0,1+i,1)
  dinic.addedge(n+1+i,2*n+1,1)
for i in range(n):
  for j in range(n):
    if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
      dinic.addedge(1+i,n+1+j,1)
print(dinic.flow(0,2*n+1))

Submission status: Accepted

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

INF = 1000000000
min_dif = INF
min_index = -1
pair = 0

while len(blue):
    min_dif = INF
    min_index = -1
    for i in range(len(red)):
        if blue[0][0] > red[i][0] and blue[0][1] > red[i][1]:
            dif = blue[0][1] - red[i][1]
            if dif < min_dif:
                min_dif = dif
                min_index = i
    blue.pop(0)
    if min_index != -1:
        red.pop(min_index)
        pair += 1


print(pair)

Submission status: Accepted

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

cnt = 0
for i in range(N):
	temp_y = -1
	temp_ind = -1
	for j in range(len(R)):
		if R[j][0] < B[i][0] and R[j][1] < B[i][1] and R[j][1] > temp_y:
			temp_y = R[j][1]
			temp_ind = j
	if temp_ind != -1:
		cnt += 1
		R.pop(temp_ind)
print(cnt)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

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

N = I()
a,b = Line(N)
c,d = Line(N)

x = []
for i in range(N):
    x.append([a[i],b[i],0])
    x.append([c[i],d[i],1])

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

use = {}
for i in range(2*N):
    use[i] = False

ans = 0
for i in range(2*N)[::-1]:
    if x[i][2] != 0:
        continue
    else:
        index = 2*N
        val = float('inf')
        for j in range(i+1,2*N):
            if x[j][1]>x[i][1] and x[j][1]<val and use[j]!=True and x[j][2]==1:
                index = j
                val = x[j][1]
        if index != 2*N:
            ans += 1
            use[index] = True

print(ans)

Submission status: Accepted

Solution code:
import sys
from statistics import *
from collections import *
from operator import itemgetter
stdin = sys.stdin

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

n = ni()
red = []
blue = []
for i in range(n):
    li = na()
    li.append(0)
    red.append(li)
for i in range(n):
    li = na()
    li.append(0)
    blue.append(li)
red = sorted(red, key=itemgetter(1))
blue = sorted(blue, key=itemgetter(0))
ct = 0
for i in range(n):
    c, d, r = blue[i]
    for j in range(n)[::-1]:
        a, b, l = red[j]
        if r == 0 and l == 0 and a < c and b < d:
            ct += 1
            red[j][2] = 1
            blue[i][2] = 1
            break
print(ct)

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.sort(key=itemgetter(1), reverse=True)
ab.sort(key=itemgetter(0), reverse=True)
cd.sort(key=itemgetter(0), reverse=False)
cd.sort(key=itemgetter(1), reverse=False)

reserved = [0 for _ in range(N)]
for a, b in ab:
    for i, (c, d) in enumerate(cd):
        if reserved[i] :
            continue
        if a<c and b<d :
            reserved[i] = 1
            break
print(sum(reserved))

Submission status: Accepted

Solution code:
n = int(input())
rd = []
bl = []
for _ in range(n):
    a, b = map(int,input().split())
    rd.append([a,b])
for _ in range(n):
    c, d = map(int,input().split())
    bl.append([c,d])
bl.sort()
used_r = [0] * n
ans = 0

for i in range(n):
    y = -1
    pair = -1
    for j in range(n):
        if rd[j][0] < bl[i][0] and rd[j][1] < bl[i][1] and rd[j][1] > y and used_r[j] == 0:
            y = rd[j][1]
            pair = j
    if pair != -1:
        used_r[pair] = 1
        ans += 1
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)]
a1 = sorted(a, key = lambda x:x[0])
b1 = sorted(b, key = lambda x:x[0])

inum = []
for j in range(n):
    bench = []
    for i in range(n):
        if a1[i] not in inum:
            if a1[i][0]< b1[j][0] and a1[i][1]< b1[j][1]:
                bench.append(a1[i])
    if bench:
        inum.append(max(bench, key=lambda x:x[1]))
print(len(inum))

Submission status: Accepted

Solution code:
N = int(input())
red_ps  = []
blue_ps = []
for i in range(N):
    red_ps.append(list((map(int,input().split()))))
for i in range(N):
    blue_ps.append(list((map(int,input().split()))))
    
red_ps.sort(key = lambda p: p[0], reverse = True)
blue_ps.sort(key = lambda p: p[1], reverse = False)

count = 0

for blue_p in blue_ps:
    for i,red_p in enumerate(red_ps):
        if red_p[0] < blue_p[0] and red_p[1] < blue_p[1]:
            count += 1
            red_ps.pop(i)
            break

print(count)