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:
# greedy

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

"""
赤点のx座標 < 青点のx座標 and 赤点のy座標 < 青点のy座標
その中で赤点のy座標は最大のものを選ぶ
"""

sort_red = sorted(red, key=lambda x:x[1], reverse=True) # y座標で降順ソート
sort_blue = sorted(blue, key=lambda x:x[0]) # x座標で昇順ソート

ans = 0
for i in range(N):
  for j in range(len(sort_blue)):
    if (sort_red[i][0] < sort_blue[j][0] and 
        sort_red[i][1] < sort_blue[j][1]):
      ans += 1
      del sort_blue[j]
      break
print(ans)

Submission status: Accepted

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

a.sort(reverse=True)
b.sort()
idxb = list()
for i in range(n):
    idx = -1
    miny = 1e+9
    for j in range(n):
        if not j in idxb:
            if a[i][0] < b[j][0] and a[i][1] < b[j][1] < miny:
                miny = b[j][1]
                idx = j
    if idx != -1:
        idxb.append(idx)

print(len(idxb))

Submission status: Accepted

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

a.sort(reverse=True)
b.sort()
idxb = list()
for i in range(n):
    idx = -1
    maxy = -1
    for j in range(n):
        if not j in idxb:
            if a[j][0] < b[i][0] and maxy < a[j][1] < b[i][1] :
                maxy = a[j][1]
                idx = j
    if idx != -1:
        idxb.append(idx)

print(len(idxb))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
R = [list(map(int, input().split(' '))) for _ in range(N)]
B = [list(map(int, input().split(' '))) for _ in range(N)]

B.sort(key=lambda x: x)


ans = 0
used = set()
for c, d in B:
    candidates = [(a, b, i) for i, (a, b) in enumerate(R)
                    if i not in used and a < c and b < d]

    if len(candidates) > 0:
        candidates.sort(key= lambda x: -x[1])
        # print(candidates)
        used.add(candidates[0][2])

# print(used)
print(len(used))

Submission status: Accepted

Solution code:
N, *I = map(int, open(0).read().split())
AB = set(zip(*[iter(I[:2 * N])] * 2))
CD = sorted(zip(*[iter(I[2 * N:])] * 2))

for c, d in CD:
    ma = max(((a, b) for a, b in AB if a < c and b < d), key=lambda x: x[1], default=None)
    if ma:
        AB.remove(ma)

print(N - len(AB))

Submission status: Accepted

Solution code:
N, *I = map(int, open(0).read().split())
AB = list(zip(*[iter(I[:2 * N])] * 2))
CD = sorted(zip(*[iter(I[2 * N:])] * 2))

for c, d in CD:
    ma = max(((a, b) for a, b in AB if a < c and b < d), key=lambda x: x[1], default=None)
    if ma:
        AB.remove(ma)

print(N - len(AB))

Submission status: Accepted

Solution code:
from operator import itemgetter

N=int(input())
A=[]
B=[]
for i in range(N):
  temp=list(map(int, input().split()))
  A.append(temp)
for i in range(N):
  temp=list(map(int, input().split()))
  B.append(temp)
  

def main():
  A.sort(key=itemgetter(0,1))
  B.sort(key=itemgetter(0,1))
  #print(A)
  #print(B)
  cnt=0
  while B!=[]:
    idx=-1
    y=-1
    for i in range(len(A)):
      if A[i][0]>=B[0][0]:
        break
      if A[i][1]<B[0][1] and y<=A[i][1]:
        idx=i
        y=A[i][1]
    if idx!=-1:
      cnt+=1
      #print(A[idx],B[0])
      del A[idx]
      del B[0]
    else:
      del B[0]
  print(cnt)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
red=[list(map(int,input().split())) for _ in range(N)]
blu=[list(map(int,input().split())) for _ in range(N)]

red.sort(key=lambda x:x[1],reverse=True)
blu.sort()
cnt=0
for b in blu:
    for r in red:
        #print(r,b)
        if r[0]<b[0] and r[1]<b[1]:
            cnt+=1
            r[0]=10000
            r[1]=10000
            break
print(cnt)
#print(blu)

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

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

RED.sort(key=lambda x: -x[0]) #x座標が大きい順
BLUE.sort(key=lambda x: x[1]) #y標が小さい順

# print(RED, BLUE)
SELECTED_RED = set()
SELECTED_BLUE = set()

for i in range(N):
  for j in range(N):
    if i in SELECTED_RED or j in SELECTED_BLUE:
       continue
    
    a, b = RED[i]
    c, d = BLUE[j]
    if a < c and b < d:
      # d以下の最大のy座標はbである
      SELECTED_RED.add(i)
      SELECTED_BLUE.add(j)

print(len(SELECTED_RED))

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

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

RED.sort(key=lambda x: -x[1]) #y座標が大きい順
BLUE.sort(key=lambda x: x[0]) #x座標が小さい順

# print(RED, BLUE)
SELECTED_RED = set()
SELECTED_BLUE = set()

for i in range(N):
  for j in range(N):
    if i in SELECTED_RED or j in SELECTED_BLUE:
       continue
    
    a, b = RED[i]
    c, d = BLUE[j]
    if a < c and b < d:
      # d以下の最大のy座標はbである
      SELECTED_RED.add(i)
      SELECTED_BLUE.add(j)

print(len(SELECTED_RED))

Submission status: Accepted

Solution code:
"""
最大フローとして解き直してみる
"""

from collections import deque
from collections import defaultdict
class Dinic:
    def __init__(self):
        self.G = defaultdict(list)
    
    def add_edge(self, fr, to, cap):
        """
        :param fr: 始点
        :param to: 終点
        :param cap: 容量
        """
        # forwardの最後には、キャパのうちどれだけ使ったかが入る
        forward = [to, cap, None]
        backward = [fr, 0, forward]
        forward[-1] = backward
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        """
        :param v1: 始点
        :param v2: 終点
        :param cap1: 容量1
        :param cap2: 容量2
        """
        edge1 = [v2, cap1, None]
        edge2 = [v1, cap2, edge1]
        edge1[-1] = edge2
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        """
        :param s: bfsの始点(source)
        :param t: bfsの終点(sink)
        :return: tに到達したかどうか。(sourceからの距離を保存しながら)
        """
        self.level = level = defaultdict(int)
        q = deque([s])
        level[s] = 1
        G = self.G
        while len(q) > 0:
            v = q.popleft()
            lv = level[v] + 1
            nexts = G[v]
            for w, cap, _ in nexts:
                if cap > 0 and level[w] == 0:
                    level[w] = lv
                    q.append(w)
        is_reach = (level[t] > 0)
        return is_reach

    def dfs(self, v, t, f):
        """
        :param v: 点v
        :param t: 終点(sink)
        :param f: v時点でのフロー
        :return: 終点到達時のフローを返す
        """   
        if v == t:
            return f
        level = self.level
        nexts = self.G[v]
        for edge in nexts:
            w, cap, rev = edge
            # まだキャパがあるならば
            if cap > 0 and level[v] < level[w]:
                # キャパが余ってるなら全部流すし
                # カツカツならキャパのmaxまで流す
                d = self.dfs(w, t, min(f, cap))
                # 帰りがけに、更新
                if d > 0:
                    # 順方向のキャパをd下げる
                    # 逆方向のキャパをd増やす
                    edge[1] -= d
                    rev[1] += d
                    return d
        # 次の道が見つからなければ終了
        return 0
    
    def flow(self, s, t):
        """
        :param s: 始点
        :param t: 終点
        :return : 最大フロー
        """
        flow = 0
        INF = 10**10
        G = self.G
        # ルートが存在する限り、続ける
        while self.bfs(s, t):
            f = INF
            while f > 0:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

# 入力受け取り
N = int(input())
dinic = Dinic()
reds = []
for i in range(N):
    a,b = map(int, input().split())
    reds.append((a,b))
blues = []
for i in range(N):
    a,b = map(int, input().split())
    blues.append((a,b))

# マッチングできるペアをグラフに。(red=blueの二部グラフになる。)
cnt = 0
edges = defaultdict(list)
source = "s"
sink = "t"
# source -> 各青の頂点へ
for i in range(len(blues)):
    dinic.add_edge(source,i,1)
# 各赤の頂点 -> sink
for j in range(len(reds)):
    dinic.add_edge(j+N, sink, 1)
    
for i,(c,d) in enumerate(blues):
    for j,(a,b) in enumerate(reds):
        if c > a and d > b:
            dinic.add_edge(i, N+j, 1)

ans = dinic.flow(source, sink)
print(ans)

Submission status: Accepted

Solution code:
"""
最大フローとして解き直してみる
"""

from collections import deque
from collections import defaultdict
class Dinic:
    def __init__(self):
        # self.N = N
        self.G = defaultdict(list)
    
    def add_edge(self, fr, to, cap):
        """
        :param fr: 始点
        :param to: 終点
        :param cap: 容量
        """
        # forwardの最後には、キャパのうちどれだけ使ったかが入る
        forward = [to, cap, None]
        backward = [fr, 0, forward]
        forward[-1] = backward
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        """
        :param v1: 始点
        :param v2: 終点
        :param cap1: 容量1
        :param cap2: 容量2
        """
        edge1 = [v2, cap1, None]
        edge2 = [v1, cap2, edge1]
        edge1[-1] = edge2
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        """
        :param s: bfsの始点(source)
        :param t: bfsの終点(sink)
        :return: tに到達したかどうか。(sourceからの距離を保存しながら)
        """
        self.level = level = [-1]*len(self.G)
        q = deque([s])
        level[s] = 0
        G = self.G
        while len(q) > 0:
            v = q.popleft()
            lv = level[v] + 1
            nexts = G[v]
            for w, cap, _ in nexts:
                if cap > 0 and level[w] == -1:
                    level[w] = lv
                    q.append(w)
        is_reach = (level[t] > 0)
        return is_reach

    def dfs(self, v, t, f):
        """
        :param v: 点v
        :param t: 終点(sink)
        :param f: v時点でのフロー
        :return: 終点到達時のフローを返す
        """   
        if v == t:
            return f
        level = self.level
        nexts = self.G[v]
        for edge in nexts:
            w, cap, rev = edge
            # まだキャパがあるならば
            if cap > 0 and level[v] < level[w]:
                # キャパが余ってるなら全部流すし
                # カツカツならキャパのmaxまで流す
                d = self.dfs(w, t, min(f, cap))
                # 帰りがけに、更新
                if d > 0:
                    # 順方向のキャパをd下げる
                    # 逆方向のキャパをd増やす
                    edge[1] -= d
                    rev[1] += d
                    return d
        # 次の道が見つからなければ終了
        return 0
    
    def flow(self, s, t):
        """
        :param s: 始点
        :param t: 終点
        :return : 最大フロー
        """
        flow = 0
        INF = 10**10
        G = self.G
        # ルートが存在する限り、続ける
        while self.bfs(s, t):
            f = INF
            while f > 0:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

# 入力受け取り
N = int(input())
dinic = Dinic()
reds = []
for i in range(N):
    a,b = map(int, input().split())
    reds.append((a,b))
blues = []
for i in range(N):
    a,b = map(int, input().split())
    blues.append((a,b))

# マッチングできるペアをグラフに。(red=blueの二部グラフになる。)
cnt = 0
edges = defaultdict(list)
source = 2*N
sink = 2*N+1
# source -> 各青の頂点へ
for i in range(len(blues)):
    dinic.add_edge(source,i,1)
# 各赤の頂点 -> sink
for j in range(len(reds)):
    dinic.add_edge(j+N, sink, 1)
    
for i,(c,d) in enumerate(blues):
    for j,(a,b) in enumerate(reds):
        if c > a and d > b:
            dinic.add_edge(i, N+j, 1)

ans = dinic.flow(source, sink)
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

# reds = sorted(reds,key=itemgetter(0,1),reverse=True)
# blues = sorted(blues,key=itemgetter(1))
# blues = sorted(blues,reverse=True)


cnt = 0
from collections import defaultdict
edges = defaultdict(list)
for i,(c,d) in enumerate(blues):
    for j,(a,b) in enumerate(reds):
        if c > a and d > b:
            edges[i].append(j+N)
            edges[j+N].append(i)
            
            
# print(edges)
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
# xn, yn, e = map(int, input().split())
# edges = [set() for _ in range(xn)]
matched = [-1] * 2*N
 
# for _ in range(e):
#     x, y = map(int, input().split())
#     edges[x].add(y)
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(N)))

Submission status: Accepted

Solution code:
n = int(input())
red = []
blue = []
for i in range(n):
    red.append(list(map(int, input().split())))
for i in range(n):
    blue.append(list(map(int, input().split())))
#xの昇順のソート
red.sort(key=lambda x:x[0])
blue.sort(key=lambda x:x[0])
ans = 0
delete_value = set([-1])
for b in range(n):
    maxY = -1
    for r in range(n):
        if blue[b][0] < red[r][0]:
            break
        else:
            if blue[b][1] > red[r][1] and red[r][1] not in delete_value:
                maxY = max(maxY, red[r][1])
    delete_value.add(maxY)
print(len(delete_value)-1)

Submission status: Accepted

Solution code:
N = int(input())
pointR = []
pointB = []
for i in range(N):
    pointR.append(list(map(int, input().split())))
for i in range(N):
    pointB.append(list(map(int, input().split())))
pointR.sort(key = lambda t: t[0], reverse = True)
pointB.sort(key = lambda t: t[1])
ans = 0

Rok = [True] * N

for i in range(N):
    for j in range(N):
        if Rok[j]:
            if pointR[j][0] < pointB[i][0] and pointR[j][1] < pointB[i][1]:
                ans += 1
                Rok[j] = False
                break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
pointR = []
pointB = []
for i in range(N):
    pointR.append(list(map(int, input().split())))
for i in range(N):
    pointB.append(list(map(int, input().split())))
pointR.sort(key = lambda t: t[0], reverse = True)
pointB.sort(key = lambda t: t[1])
ans = 0

Aok = [True] * N

for i in range(N):
    for j in range(N):
        if Aok[j]:
            if pointR[j][0] < pointB[i][0] and pointR[j][1] < pointB[i][1]:
                ans += 1
                Aok[j] = False
                break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
pointR = []
pointB = []
for i in range(N):
    pointR.append(list(map(int, input().split())))
for i in range(N):
    pointB.append(list(map(int, input().split())))
pointR.sort(key = lambda t: t[0], reverse = True)
pointB.sort(key = lambda t: t[1])
ans = 0

Aok = [True] * N
Bok = [True] * N

for i in range(N):
    for j in range(N):
        if Aok[j] and Bok[i]:
            if pointR[j][0] < pointB[i][0] and pointR[j][1] < pointB[i][1]:
                ans += 1
                Aok[j] = False
                Bok[i] = False
                break
print(ans)

Submission status: Accepted

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

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

    red.sort(key=lambda x: -x[1]) #y座標が大きい順
    blue.sort(key=lambda x: x[0]) #x座標が小さい順
    j_list = []
    for i in range(N):
        c,d =blue[i]

        for j in range(N):
            a,b = red[j]
            if j in j_list:
                continue

            if a<c and b<d:
                # d以下の最大のy座標はbである
                j_list.append(j)
                break
    print(len(j_list))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())
red = [tuple(map(int,input().split(" ")))  for _ in range(N)]
blue = [tuple(map(int,input().split(" ")))  for _ in range(N)]
blue = sorted(blue,key=lambda x: (x[0],x[1] ) )
red= sorted(red,key=lambda x: (-x[1],x[0] ) )

ans = 0
for b in blue:
    bx,by = b
    for i,r in enumerate(red):
        rx,ry = r
        if bx > rx and by > ry:
            ans += 1
            red.pop(i)
            break


print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
R = [list(map(int, input().split())) for i in range(n)]
B = sorted([list(map(int, input().split())) for _ in range(n)], key = itemgetter(0))
pair = 0

for b in B:
   L = [r for r in R if r[0] < b[0] and r[1]<b[1]]
   if len(L) != 0:
       s = L[0]
       for l in L:
           if s[1] < l[1]:
               s = l
       R.remove(s)
       pair += 1
           
print(pair)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    ab = [[] for _ in range(N)]
    cd = ab[:]
    for i in range(N):
        ab[i] = list(map(int, input().split()))
    for i in range(N):
        cd[i] = list(map(int, input().split()))
    
    ab.sort(key=lambda x: -x[0])
    cd.sort(key=lambda x: (x[0], -x[1]))
    
    ans = 0
    used = [0 for _ in range(N)]
    for i in range(N):
        use, d_min = -1, 201
        for j in range(N):
            if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1]:
                if cd[i][1] - ab[j][1] < d_min:
                    if used[j] == 0:
                        use = j
                        d_min = cd[i][1] - ab[j][1]
        if use != -1:
            used[use] = 1
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bi_l

n = int(sys.stdin.readline().rstrip())
I = list(zip(*[map(int, sys.stdin.read().split())] * 2))
red = I[:n]
blue = I[n:]

def main():
    red.sort(key=lambda x: x[0])
    blue.sort(key=lambda x: x[0])
    a = []
    b = []
    for x, y in red:
        a.append(x)
        b.append(y)
    
    paired = [False] * n
    cnt = 0
    for c, d in blue:
        pair = None
        res = -1
        for i in range(bi_l(a, c)):
            if not paired[i] and b[i] < d and b[i] > res:
                pair = i
                res = b[i]
        if not pair is None:
            paired[pair] = True
            cnt += 1
    
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
abcd = list(zip(*[map(int, sys.stdin.read().split())] * 2))
ab = abcd[:n]
cd = abcd[n:]

def main():
    abcd.sort(key=lambda x: x[0])
    blue = list(map(lambda x: x[1], abcd))
    ab.sort(key=lambda x: x[0], reverse=True)
    reversed_b_sorted_by_a = list(map(lambda x: x[1], ab))
    
    cnt = 0
    for b in reversed_b_sorted_by_a:
        i = blue.index(b)
        if i == len(blue) - 1:
            blue.remove(b)
            continue
        cand = [x for x in blue[i+1:] if x > b]
        if not cand:
            blue.remove(b)
            continue
        blue.remove(b)
        blue.remove(min(cand))
        cnt += 1

    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
R=[list(map(int,input().split())) for _ in range(n)]
B=[list(map(int,input().split())) for _ in range(n)]
B.sort()
ans=0
for b in B:
    L = [ r for r in R if r[0]<b[0] and r[1]<b[1]]
    if len(L)!=0:
        s = L[0]
        for l in L:
            if s[1]<l[1]: s=l
        R.remove(s)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
R=[list(map(int,input().split())) for _ in range(n)]
B=[list(map(int,input().split())) for _ in range(n)]
B.sort()
ans=0
for b in B:
    L = [ r for r in R if r[0]<b[0] and r[1]<b[1]]
    if len(L)!=0:
        s = L[0]
        for l in L:
            if s[1]<l[1]: s=l
        R.remove(s)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
r = sys.stdin.readline
N = int(r())
red = []
blue = []
for i in range(N):
    a, b = list(map(int, r().split()))
    red.append([a, b])
for i in range(N):
    c, d = list(map(int, r().split()))
    blue.append([c, d])

xblue = sorted(blue, key=lambda x: x[0])

i = 0
j = 0
ii = [True for i in range(2*N+1)]
jj = [True for i in range(2*N+1)]
ans = 0
for i in range(N):
    m = [-100000, -100000]
    for j in range(N):
        if ii[i] and jj[j] and red[j][0] < xblue[i][0] and red[j][1] < xblue[i][1]:
            if m[0] < red[j][1]:
                m[0] = red[j][1]
                m[1] = j
    if m[0] != -100000 and m[1] != -100000:
        ii[i] = False
        jj[m[1]] = False
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

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

red_points.sort(key=lambda x:(x[1]*-1))
blue_points.sort()

blue_cursor = 0
pair_cnt = 0

for bx,by in blue_points:
    for i,(ax,ay) in enumerate(red_points):
        if ax < bx and ay < by:
            pair_cnt+=1
            red_points.pop(i)
            break

print(pair_cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ba = []
cd = []
for i in range(n):
  a, b = map(int, input().split())
  ba.append([b, a])
for j in range(n):
  c, d = map(int, input().split())
  cd.append([c, d])
ba.sort(reverse = True)
cd.sort()
ans = 0
for c, d in cd:
  for i in range(n):
    b, a = ba[i]
    if a < c and b < d:
      ans += 1
      ba[i] = [201, 201]
      break
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
# 2部グラフの最大流問題で解く
N = int(input())
NN = N * 2
XY = [[int(x) for x in input().split()] for _ in range(NN)]

graph = [[0] * (NN+2) for _ in range(NN+2)]
start = NN
goal = NN + 1

for i,(a,b) in enumerate(XY[:N]):
  for j,(c,d) in enumerate(XY[N:],N):
    if a < c and b < d:
      graph[i][j] = 1

for i in range(N):
  graph[start][i] = 1
for i in range(N,NN):
  graph[i][goal] = 1

INF = 10 ** 9

def max_flow(graph):
  dist,pred = dijkstra(graph,indices = start,return_predecessors = True)
  if dist[goal] > INF:
    return 0
  y = goal
  while y != start:
    x = pred[y]
    graph[x][y] -= 1
    graph[y][x] += 1
    y = x
  return 1 + max_flow(graph)

answer = max_flow(graph)
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

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)]
usedab=[0]*n
usedcd=[0]*n
cd.sort();ab.sort(key=lambda tup:-tup[1])
for i,(c,d) in enumerate(cd):
    for j,(a,b) in enumerate(ab):
        if a<c and b<d and (not usedab[j]) and (not usedcd[i]):
            usedab[j]=1
            usedcd[i]=1
            count+=1
            # print(a,b,c,d)
print(count)
# print(usedab)
# print(usedcd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
rp=np.array([list(map(int, input().split())) for i in range(N)])
bp=np.array([list(map(int, input().split())) for i in range(N)])
rp=rp[np.argsort(rp[:, 0])]
bp=bp[np.argsort(bp[:, 0])]
rp=np.c_[rp, np.arange(N).reshape(-1, 1)]
bp=np.c_[bp, np.arange(N).reshape(-1, 1)]

counter=0
for i in range(N):
  temp=rp[rp[:, 0]<bp[i, 0], :]
  if temp.shape[0]>0:
    temp=temp.reshape(-1, 3)
  if temp.shape[0]>0:
    temp=temp[temp[:, 2]!=-1, :]
    temp=temp.reshape(-1, 3)
  if temp.shape[0]>0:
    temp=temp[temp[:, 1]<bp[i, 1], :]
    temp=temp.reshape(-1, 3)
  if temp.shape[0]>1:
    temp=temp[np.argmax(temp[:, 1]), :]
    temp=temp.reshape(1, 3)
  if temp.shape[0]==1:
    counter+=1
    rp[temp[0, 2], 2]=-1
    
print(counter)

Submission status: Accepted

Solution code:
from collections import deque

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

while len(CD)>0:
    p=CD.popleft()
    c,d=p[0],p[1]
    for i in range(len(AB)):
        if AB[i][0]<c and AB[i][1]<d:
            AB=AB[:i]+AB[i+1:]
            cc+=1
            break

print(cc)

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(2*N+2)]

for i in range(N):
    forward = [2+i,1,None]
    forward[2] = backward = [0,0,forward]
    graph[0].append(forward)
    graph[2+i].append(backward)

for i in range(N):
    forward = [1,1,None]
    forward[2] = backward = [2+N+i,0,forward]
    graph[2+N+i].append(forward)
    graph[1].append(backward)

for i in range(N):
    for j in range(N):
        if R[i][0]<B[j][0] and R[i][1]<B[j][1]:
            forward = [2+N+j,1,None]
            forward[2] = backward = [2+i,0,forward]
            graph[2+i].append(forward)
            graph[2+N+j].append(backward)

flow = 0

while True:

    queue = deque([0])
    level = [None for _ in range(2*N+2)]
    level[0] = 0

    while queue:
        node = queue.popleft()
        for adj,adjcap,_ in graph[node]:
            if adjcap>0 and level[adj] is None:
                level[adj] = level[node]+1
                queue.append(adj)

    if level[1] is None:
        break

    stack = [0]
    visited = [0 for _ in range(2*N+2)]
    visited[0] = 1
    parent = [None for _ in range(2*N+2)]
    parent[0] = 0

    while stack:
        node = stack.pop()
        for adj,adjcap,adjrev in graph[node]:
            if not visited[adj] and adjcap>0 and level[node]<level[adj]:
                visited[adj] = 1
                parent[adj] = node
                stack.append(adj)

    if visited[1]:
        flow += 1
        present = 1
        prev = parent[present]
        while present != 0:
            for g in graph[prev]:
                adj,adjcap,adjrev = g
                if adj == present:
                    g[1] = 0
                    adjrev[1] = 1
            present = prev
            prev = parent[present]

print(flow)

Submission status: Accepted

Solution code:
n = int(input())
l1 = [[int(i) for i in input().split()] for i in range(n)]
l2 = [[int(i) for i in input().split()] for i in range(n)]
l1.sort(key=lambda x:x[0],reverse=True)
l2.sort(key=lambda x:x[1])

answer = 0
for a,b in l1:
    for c,d in l2:
        if a < c and b < d:
            answer += 1
            l2.remove([c,d])
            break

print(answer)

Submission status: Accepted

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

res = 0
for bx, by in blue:
    tmp_max = -1
    tmp_cnt = None
    for i, (rx, ry) in enumerate(red):
        if bx <= rx:
            break
        if tmp_max <= ry < by:
            tmp_max = ry
            tmp_cnt = i
    if tmp_cnt is not None:
        res += 1
        red.pop(tmp_cnt)

print(res)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]
red.sort(key=itemgetter(1), reverse=True)
blue.sort()
red_flag = [False] * n
for i in range(n):
    pair_red_index = float('inf')
    for j in range(n):
        if not (red_flag[j]) and red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
            pair_red_index = j
            break
    if pair_red_index != float('inf'):
        red_flag[pair_red_index] = True
print(red_flag.count(True))

Submission status: Accepted

Solution code:
n = int(input())
reds = sorted((tuple(map(int, input().split())) for _ in range(n)), key=lambda tuple_: tuple_[1], reverse=True)
blues = sorted((tuple(map(int, input().split())) for _ in range(n)), key=lambda tuple_: tuple_[0])

pairs = 0
for blue in blues:
    for idx, red in enumerate(reds):
        if red[0] < blue[0] and red[1] < blue[1]:
            break
    else:
        continue
    del reds[idx]
    pairs += 1

print(pairs)

Submission status: Accepted

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

pairs = 0
for blue in blues:
    red_max_y = -float("inf")
    arg_max = -1
    for idx, red in enumerate(reds):
        if red[0] < blue[0] and red[1] < blue[1]:
            if red[1] > red_max_y:
                red_max_y = red[1]
                arg_max = idx
    if arg_max != -1:
        del reds[arg_max]
        pairs += 1

print(pairs)