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:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

sys.setrecursionlimit(10000000)

N = int(input())
AB = []
CD = []

for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))

for i in range(N):
    C, D = map(int, input().split())
    CD.append((C, D))

AB.sort()
CD.sort()

used = [False] * N
cnt = 0

for i in range(N):
    m = -1
    for j in range(N):
        if not used[j] and CD[i][0] > AB[j][0] and CD[i][1] > AB[j][1]:
            if m < 0 or AB[m][1] < AB[j][1]:
                m = j

    if m >= 0:
        used[m] = True
        cnt += 1

print(cnt)

Submission status: Accepted

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

R.sort(reverse=True)#aをx座標でソート
B.sort(key = lambda x:x[1])#bをｙ座標でソート
ans = 0
for i in R:
    for j in range(len(B)):
        if i[0] < B[j][0] and i[1] < B[j][1]:
            ans += 1
            B.pop(j)
            break

print(ans)

Submission status: Accepted

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


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

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

  for ib, b in enumerate(B):
    bx, by = b[0], b[1]

    tmp_r = (-1, -1)

    for ir, r in enumerate(R):
      rx, ry = r[0], r[1]

      if rx < bx and \
         ry < by and \
         tmp_r[1] < ry:
         # b[0] - r[0] < tmp_b[0] - r[0] and \
         # b[1] - r[1] < tmp_b[1] - r[1]:
        tmp_r = r

    if tmp_r == (-1, -1):
      continue
    num_friends += 1
    R.remove(tmp_r)

  print(num_friends)


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

Submission status: Accepted

Solution code:

from collections import deque
N = int(input())
Y = {}
for _ in range(N):
    c,d = map(int,input().split())
    Y[c] = d  
X = []
for _ in range(N):
    a,b = map(int,input().split())
    X.append([a,b])

X.sort()
dq = deque(X)
cnt =0
while dq:
    x,y = dq.popleft()
    sorted_Y = sorted(Y.items(),reverse=True, key = lambda x:x[1])
    for key,val in sorted_Y:
        if key <x and val<y:
            cnt += 1
            del Y[key]
            break
    
print(cnt)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N_s = getN()
A = [getList() for i in range(N_s)]
B = [getList() for i in range(N_s)]
query = []
# ノードの始点を2 * N_sに、終点を2 * N_s + 1に設定
for i in range(N_s):
    query.append([2 * N_s, i, 1])
    query.append([N_s + i, 2 * N_s + 1, 1])
for i in range(N_s):
    for j in range(N_s):
        if A[i][0] < B[j][0] and A[i][1] < B[j][1]:
            query.append([i, N_s + j, 1])

N = 2 * N_s + 2

ans = 0
lines = defaultdict(set)
cost = [[0] * N for i in range(N)]
for i in range(len(query)):
    a, b, c = query[i]
    lines[a].add(b)
    cost[a][b] += c

# 二部マッチング問題なので最大流
# staからスタート
def Ford_Fulkerson(sta, end):
    global ans
    queue = deque()
    queue.append([sta, float('inf')])

    ignore = [1] * N
    ignore[sta] = 0

    route = [0] * N
    route[sta] = -1

    while queue:
        s, flow = queue.pop()
        for t in lines[s]:  #s->t
            if ignore[t]: #未到達
                # flowは入ってくる量、出る量のうち小さい方
                flow = min(cost[s][t], flow)
                route[t] = s
                queue.append([t, flow])
                ignore[t] = 0
                if t == end: #ゴール到達
                    ans += flow
                    break
        else:
            continue #breakされなければWhile節の先頭に戻る
        # Falseはされない
        break
    else:
        return False

    t = end
    s = route[t]
    # goalまで流れた量はflow
    # 逆向きの辺を貼る
    while s != -1:
        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)
            #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)

        cost[t][s] += flow

        # 一つ上の辺をたどる
        t = s
        s = route[t]

    return True

while True:
    # ちょびちょび流して行ってゴールまで流れなくなったら終了
    if Ford_Fulkerson(N - 2, N - 1):
        continue
    else:
        break

print(ans)

Submission status: Accepted

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

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[j].append([pab[1],i])
        
ans = 0
s = set()

for gg in g:
    gg.sort(reverse=True)
    for ggg in gg:
        if ggg[1] in s:continue
        else:
            ans += 1
            s.add(ggg[1])
            break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=[list(map(int,input().split())) for _ in range(N)]
c=[list(map(int,input().split())) for _ in range(N)]
X=[(q,w,0) for q,w in a]+[(e,r,1) for e,r in c]
X.sort()
ans=0
dp=[0]*(2*N)
for x,y,z in X:
  if z==0:
    dp[y]+=1
  else:
    for v in range(y-1,-1,-1):
      if dp[v]>0:
        ans+=1
        dp[v]-=1
        break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red, blue = [], []
ans = 0
for _ in range(n):
    a, b = map(int, input().split())
    red.append((max(a, b), a, b))
for _ in range(n):
    c, d = map(int, input().split())
    blue.append((min(c, d), c, d))
red.sort(key=lambda x: x[0], reverse=True)
blue.sort(key=lambda x: x[0])
for i in range(n):
    _, xb, yb = blue[i]
    for j in range(n):
        if red[j]:
            _, xr, yr = red[j]
            if xb > xr and yb > yr:
                red[j] = False
                ans += 1
                break
print(ans)

Submission status: Accepted

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

g = [[0 for _ in range(2*n+2)] for _ in range(2*n+2)]

for (i, (a, b)) in enumerate(ab):
    fr = i+2
    g[0][fr] = 1
    for (j, (c, d)) in enumerate(cd):
        to = n+j+2
        g[to][1] = 1
        if a < c and b < d:
            g[fr][to] = 1

used = [False for _ in range(2 * n + 2)]
path = []
goal = 1
flow = [[0 for _ in range(2*n+2)] for _ in range(2*n+2)]


def bfs(v):
    used[v] = True
    for next in range(2 * n + 2):
        if g[v][next] == 0 or used[next]:
            pass
        elif next == goal:
            path.append(v)
            return True
        elif bfs(next):
            path.append(v)
            return True
    return False


ans = 0
while bfs(0):
    path.reverse()
    path.append(1)
    for i in range(len(path) - 1):
        g[path[i]][path[i + 1]] -= 1
        g[path[i + 1]][path[i]] += 1
    used = [False for _ in range(2 * n + 2)]
    path = []
    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)]
x = []
for i,j in a:
    x.append((i,j,1))
for i,j in b:
    x.append((i,j,2))
x.sort()
#print(x)
for i in range(2*n):
    x[i] = (x[i][1],x[i][2])
#print(x)
ans = 0
while len(x):
    maxindex = 0
    maxvalue = -1
    flag = 0
    for i in range(len(x)):
        if x[i][0]>maxvalue and x[i][1]==1:
            flag = 1
            maxvalue = x[i][0]
            maxindex = i
    if flag == 0:
        break
    #if (x[maxindex][1]==1):
        #x.pop(i)
    #else:
    #maxindex2 = 0
    #maxvalue2 = -1
    flag = 0
    for i in range(maxindex+1,len(x)):
        if (x[i][1]==2):
            if (x[i][0]>maxvalue):
                ans += 1
                x.pop(i)
                x.pop(maxindex)
                flag=1
                break
    if (flag==0):
        x.pop(maxindex)
print(ans)

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

cnt = 0
i = j = 0
free_ab = [True] * n
while j < n:
    a, b = ab[i][0], ab[i][1]
    c, d = cd[j][0], cd[j][1]
    if a < c and b < d and free_ab[i]:
        cnt += 1
        free_ab[i] = False
        i = 0 
        j += 1
        continue
    elif j <= n-1 and i < n-1:
        i += 1
    elif j < n-1 and i == n-1:
        i = 0
        j += 1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    reds = [[int(item) for item in input().split()] for _ in range(N)]
    blues = [[int(item) for item in input().split()] for _ in range(N)]

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

    que = collections.deque(blues)
    cnt = 0

    while que:

        bx, by = que.popleft()

        for rx, ry in reds[:]:
            if rx <= bx and ry <= by:
                cnt += 1
                reds.remove([rx, ry])
                break
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
Nが小さいので、Y座標でcandに入れておく
"""
N = ir()
AB = [lr() for _ in range(N)]
CD = [lr() for _ in range(N)]
cand = [0] * (2*N)
ABCD = [(a, b, 0) for a, b in AB] + [(c, d, 1) for c, d in CD]
ABCD.sort()
answer = 0
for X, Y, Z in ABCD:
    if Z == 0:
        cand[Y] += 1
    else:
        for y in range(Y-1, -1, -1):
            if cand[y] > 0:
                answer += 1
                cand[y] -= 1
                break

print(answer)

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 = sorted(blue, key=lambda x: x[0])

used = []
for i in range(N):
    c, d = blue[i]
    m, tmp = -1, -1
    for j in range(N):
        if j in used:
            continue
        a, b = red[j]
        if a < c and b < d:
            if b > m:
                m = b
                tmp = j
    if tmp != -1:
        used.append(tmp)
print(len(used))

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)]
dic = {}
for a, b in ab:
    dic[(a, b)] = 0
for c, d in cd:
    dic[(c, d)] = 0

ab = sorted(ab, key=lambda x: (-x[0], -x[1]))
cd = sorted(cd, key=lambda x: (x[1], x[0]))

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

Submission status: Accepted

Solution code:
def c_2d_plane_2n_points_bipartite_graph():
    import networkx as nx
    from networkx.algorithms.flow import dinitz
    N = int(input())
    Red_point_pos = [[int(i) for i in input().split()] for j in range(N)]
    Blue_point_pos = [[int(i) for i in input().split()] for j in range(N)]

    # 1 から N 番を赤い点に割り当て，N+1 番から 2N 番を青い点に割り当てる
    # ソースを 0 番とし，シンクを 2N+1 番とする
    graph = nx.DiGraph()
    graph.add_nodes_from(range(2 * N + 2))
    for i in range(N):
        for j in range(N):
            a, b = Red_point_pos[i]
            c, d = Blue_point_pos[j]
            if a < c and b < d:  # i 番の赤い点と j 番の青い点はペアにできうる
                graph.add_edge(i + 1, j + N + 1, capacity=1)
    for i in range(1, N + 1):
        graph.add_edge(0, i, capacity=1)
    for j in range(N + 1, 2 * N + 1):
        graph.add_edge(j, 2 * N + 1, capacity=1)
    return dinitz(graph, 0, 2 * N + 1).graph['flow_value']

print(c_2d_plane_2n_points_bipartite_graph())

Submission status: Accepted

Solution code:
def c_2d_plane_2n_points_bipartite_graph():
    import networkx as nx
    from networkx.algorithms.flow import dinitz
    N = int(input())
    A, B, C, D = [], [], [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)
    for _ in range(N):
        c, d = [int(i) for i in input().split()]
        C.append(c)
        D.append(d)

    # 赤い点の番号は 1~N とし，青い点の番号は N+1~2N とする
    # ソースを 0 番とし，シンクを 2N+1 番とする
    graph = nx.DiGraph()
    graph.add_nodes_from(range(2 * N + 2))
    for i in range(N):
        for j in range(N):
            if A[i] < C[j] and B[i] < D[j]:
                graph.add_edge(i + 1, j + N + 1, capacity=1)
    for i in range(1, N + 1):
        graph.add_edge(0, i, capacity=1)
    for j in range(N + 1, 2 * N + 1):
        graph.add_edge(j, 2 * N + 1, capacity=1)

    return dinitz(graph, 0, 2 * N + 1).graph['flow_value']

print(c_2d_plane_2n_points_bipartite_graph())

Submission status: Accepted

Solution code:
N = int(input())
red = []
for i in range(N):
    a, b = map(int, input().split())
    red.append((a, b))
red = sorted(red, key=lambda x: (x[1]), reverse=True)
# print(red)

blue = []
for i in range(N):
    a, b = map(int, input().split())
    blue.append((a, b))
blue = sorted(blue, key=lambda x: (x[0], x[1]))
# print(blue)

count = 0
for i in range(N):
    b = blue[i]
    # print("{}".format(b))
    for j in range(len(red)):
        r = red[j]
        # print("{}".format(r))
        if r[0] < b[0] and r[1] < b[1]:
            # print("{}:{}".format(b, r))
            count += 1
            red.pop(j)
            break

print(count)

Submission status: Accepted

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

cb.sort(key=lambda xy: xy[0])
cr.sort(key=lambda xy: xy[1], reverse=True)

npair = 0
for (bx, by) in cb:
    for (rx, ry) in cr:
        if rx < bx and ry < by:
            npair += 1
            cr.remove((rx, ry))
            break

print(npair)

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.buffer.readline
INF = float('inf')

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

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

    AB = []
    for _ in range(N):
        a, b = map(int, readline().split())
        AB.append([a,b])

    CD = []
    for _ in range(N):
        c, d = map(int, readline().split())
        CD.append([c,d])

    dinic = Dinic(2*N+2)

    for i in range(N):
        a, b = AB[i]
        for j in range(N):
            c, d = CD[j]
            if a<c and b<d:
                dinic.add_edge(i+1,N+j+1,1)

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

    ans = dinic.flow(0, 2*N+1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Dinic's algorithm
# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html
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())
dinic = Dinic(2 * n + 2) # (始点, 終点) = (2n, 2n + 1)
AB = [list(map(int, input().split())) for _ in range(n)]
CD = [list(map(int, input().split())) for _ in range(n)]
# 条件を満たすノード同士を繋ぐ
for i in range(n):
    a, b = AB[i]
    dinic.add_edge(2 * n, i, 1)
    for j in range(n):
        if i == 0:
            dinic.add_edge(n + j, 2 * n + 1, 1)
        c, d = CD[j]
        if a < c and b < d:
            dinic.add_edge(i, n + j, 1)

print(dinic.flow(2 * n, 2 * n + 1))

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

print(p)

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_sorted_y = sorted(AB, key=lambda x: x[1])
CD_sorted_x = sorted(CD, key=lambda x: x[0])

bool_AB = [False] * n
bool_CD = [False] * n

res = 0
for i in range(n):
    c, d = CD_sorted_x[i]
    for j in range(n - 1, -1, -1):
        a, b = AB_sorted_y[j]
        if bool_CD[i] == False and bool_AB[j] == False and a < c and b < d:
            res += 1
            bool_AB[j] = True
            bool_CD[i] = True

print(res)

Submission status: Accepted

Solution code:
n=int(input())
red=[list(map(int,input().split())) for _ in range(n)]
blue=[list(map(int,input().split())) for _ in range(n)]
red.sort()
blue.sort()
 
p=0
for bb in blue:
  lis=[-1,-1]
  for rr in red:
    if rr[0]<bb[0] and rr[1]<bb[1] and lis[1]<rr[1]:
      lis=rr
  if lis!=[-1,-1]:
    red.remove(lis)
    p+=1
print(p)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
R = [tuple(map(int,input().split())) for i in range(N)]
B = [tuple(map(int,input().split())) for i in range(N)]

#ソートしてR<Bとなる点をGreedyで探索
R.sort()
B.sort()
i=0
ans=0
red_y = []
for b_x,b_y in B:
    #b_xよりxが小さいRをすべてred_yに追加
    while i<N and R[i][0]<b_x:
        bisect.insort_right(red_y,R[i][1])
        i+=1
    #r_x<b_x,r_y<b_yを満たす点があればカウント
    if red_y and red_y[0]<b_y:
        idx = bisect.bisect_right(red_y,b_y)-1
        ans+=1
        red_y.pop(idx)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
# N, K = [int(i) for i in input().split()]

red_points = []
for i in range(N):
    a, b = [int(i) for i in input().split()]
    red_points.append([a, b])
red_points_x_asc = sorted(red_points)
blue_points = []
for i in range(N):
    c, d = [int(i) for i in input().split()]
    blue_points.append([c, d])
blue_points_x_asc = sorted(blue_points)

paired_r = []
for b in blue_points_x_asc:
    b_x = b[0]
    b_y = b[1]
    r_cands = []
    for r in red_points:
        r_x = r[0]
        r_y = r[1]
        if r_x < b_x and r not in paired_r:
            r_cands.append(r)
    r_cands_y_desc = sorted(r_cands, key=lambda x: x[1], reverse=True)
    for r in r_cands_y_desc:
        r_x = r[0]
        r_y = r[1]
        if b_y > r_y:
            paired_r.append(r)
            break

print(len(paired_r))

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

print(p)

Submission status: Accepted

Solution code:
n = int(input())
AB = list(list(map(int,input().split())) for _ in range(n))
CD = list(list(map(int,input().split())) for _ in range(n))

CD.sort() # sort x in ascending order
AB.sort(key=lambda z: z[1], reverse=True) # sort x in descending order

vis_r = [False]*(n)
for b in range(n): # ascending order of x
    for r in range(n): # descending order of y
        if not vis_r[r] and AB[r][0] < CD[b][0] and AB[r][1] < CD[b][1]:
            vis_r[r] = True; break

print(sum(vis_r))

Submission status: Accepted

Solution code:
n = int(input())
AB = list(list(map(int,input().split())) for _ in range(n))
CD = list(list(map(int,input().split())) for _ in range(n))

CD.sort() # sort x in ascending order
AB.sort(key=lambda z: z[1], reverse=True) # sort x in descending order

dim_b = [[] for _ in range(n)]
for b in range(n):
    for r in range(n):
        if AB[r][0] < CD[b][0] and AB[r][1] < CD[b][1]:
            dim_b[b] += [r]

vis_r = [False]*(n)
for b in range(n): # ascending order of x
    for r in dim_b[b]: # descending order of y
        if not vis_r[r]: vis_r[r] = True; break

print(sum(vis_r))

Submission status: Accepted

Solution code:
n = int(input())
AB = list(list(map(int,input().split())) for _ in range(n))
CD = list(list(map(int,input().split())) for _ in range(n))

CD.sort() # sort x in ascending order
AB.sort(key=lambda z: z[1], reverse=True) # sort x in descending order

dim_b = [[] for _ in range(n)]
for b in range(n):
    for r in range(n):
        if AB[r][0] < CD[b][0] and AB[r][1] < CD[b][1]:
            dim_b[b] += [r]

vis_r = [False]*(n)
for b in range(n): # ascending order of x
    max_ry = max_r = -1
    for r in dim_b[b]: # descending order of y
        if vis_r[r]: continue
        if max_ry < AB[r][1]: max_ry = AB[r][1]; max_r = r
    if max_r >= 0: vis_r[max_r] = True
print(sum(vis_r))

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])
ans=0
i=0
red_x=[]
import bisect
for c,d in cd:
  while i<n and ab[i][0]<c:
    bisect.insort_right(red_x,ab[i][1])
    i+=1
  if red_x and red_x[0]<d:
    idx=bisect.bisect_right(red_x,d)-1
    ans+=1
    red_x.pop(idx)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
AB = list(list(map(int,input().split())) for _ in range(n))
CD = list(list(map(int,input().split())) for _ in range(n))

CD.sort() # sort x in ascending order
AB.sort(key=lambda z: z[1], reverse=True) # sort x in descending order

dim_b = [[] for _ in range(n)]
for b in range(n):
    bx, by = CD[b]
    for r in range(n):
        rx, ry = AB[r]
        if rx < bx and ry < by: dim_b[b] += [r]

vis_r = [False]*(n)
for b in range(n): # ascending order of x
    max_ry = max_r = -1
    for r in dim_b[b]: # descending order of y
        if vis_r[r]: continue
        rx, ry = AB[r]
        if max_ry < ry:
            max_ry = ry
            max_r = r
    if max_r >= 0: vis_r[max_r] = True
print(sum(vis_r))

Submission status: Accepted

Solution code:
n = int(input())
AB = list(list(map(int,input().split())) for _ in range(n))
CD = list(list(map(int,input().split())) for _ in range(n))

# print(*CD,sep='\n',end='\n---\n')
# print(*sorted(CD, key=lambda x: x[0]),sep='\n',end='\n---\n')
# CD.sort(key=lambda x: x[1])
# CD.sort(key=lambda x: x[0])
CD.sort()
# print(*CD,sep='\n',end='\n---\n')
# print(*AB,sep='\n',end='\n---\n')
AB.sort(key=lambda x: x[1], reverse=True)
# print(*AB,sep='\n',end='\n---\n')

dim_r = [[] for _ in range(n)]
dim_b = [[] for _ in range(n)]
# cnt_r = [0]*n
# cnt_b = [0]*n
for b in range(n):
    bx, by = CD[b]
    for r in range(n):
        rx, ry = AB[r]
        if rx < bx and ry < by:
            dim_r[r] += [b]
            dim_b[b] += [r]
            # cnt_b[b] += 1
            # cnt_r[r] += 1

# print(n)
# print(*AB,sep='\n',end='\n---\n')
# print(*CD,sep='\n',end='\n---\n')
# print(*dim_r,sep='\n',end='\n---\n')
# print(*dim_b,sep='\n',end='\n---\n')
# # print(cnt_b,end='\n---\n')

ans = 0

inf = 1000000000
vis_r = [False]*(n)
for b in range(n):
    bx, by = CD[b]
    # print('b,bx,by',b,bx,by)
    max_ry = -1
    max_r = -1
    for r in dim_b[b]:
        if vis_r[r]: continue
        # print('r,rx,ry',r,rx,ry)
        rx, ry = AB[r]
        if max_ry < ry:
            max_ry = ry
            max_r = r
    if max_r >= 0:
        # print('max_r,max_ry',max_r,max_ry)
        vis_r[max_r] = True
        ans += 1
    # print('---')
print(ans)

Submission status: Accepted

Solution code:
n, *ABCD = map(int, open(0).read().split())
AB = sorted([(a, b) for a, b in zip(ABCD[:2*n:2], ABCD[1:2*n:2])], key=lambda x:-x[1])
CD = sorted([(c, d) for c, d in zip(ABCD[2*n::2], ABCD[2*n+1::2])])

for c, d in CD:
    for i in range(len(AB)):
        a, b = AB[i]
        if a < c and b < d:
            _ = AB.pop(i)
            break
print(n-len(AB))

Submission status: Accepted

Solution code:
from operator import itemgetter
n, *ABCD = map(int, open(0).read().split())
AB = sorted([(a, b) for a, b in zip(ABCD[:2*n:2], ABCD[1:2*n:2])], key=itemgetter(1))
CD = sorted([(c, d) for c, d in zip(ABCD[2*n::2], ABCD[2*n+1::2])])

for c, d in CD:
    t_AB = [(a, b) for a, b in AB if a < c and b < d]
    if t_AB:
        AB.remove(t_AB[-1])
print(n-len(AB))

Submission status: Accepted

Solution code:
from operator import itemgetter
n, *ABCD = map(int, open(0).read().split())
AB = sorted([(a, b) for a, b in zip(ABCD[:2*n:2], ABCD[1:2*n:2])])
CD = sorted([(c, d) for c, d in zip(ABCD[2*n::2], ABCD[2*n+1::2])])

for c, d in CD:
    t_AB = [(a, b) for a, b in AB if a < c and b < d]
    if t_AB:
        t_AB.sort(key=itemgetter(1))
        AB.remove(t_AB[-1])
print(n-len(AB))

Submission status: Accepted

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

N = int(input().strip())
ab_list = [list(map(int, input().rstrip().split())) for i in range(N)]
cd_list = [list(map(int, input().rstrip().split())) for i in range(N)]
#-----

cd_list.sort()
cnt = 0

for b_x, b_y in cd_list:
    tmp_red = [ [r_x, r_y] for r_x, r_y in ab_list if (r_x < b_x) and (r_y < b_y) ]
    
    if tmp_red:
        tmp_red.sort(key= lambda x: x[1])
        
        cnt += 1
        ab_list.remove( tmp_red[-1] )

print(cnt)