Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All input values are integers.

1 \leq N \leq 100

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum number of friendly pairs.

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

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

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



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


Sample output:
2

Submission status: Accepted

Solution code:
n = int(input())
red = [[0,0] for _ in range(n)]
blue = [[0,0] for _ in range(n)]

for i in range(n):
    red[i][0], red[i][1] = map(int,input().split())
for i in range(n):
    blue[i][0], blue[i][1] = map(int,input().split())
    
red.sort(key = lambda x:-x[1])
blue.sort(key = lambda x:x[0])

flag = [True] * n

for i in range(n):
    for j in range(n):
        if flag[j] and red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
            flag[j] = False
            break

ans = 0
for i in range(n):
    if not flag[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
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])

ans=0

for b in blue:
    candi=[i for i in red if i[0]<b[0] and i[1]<b[1]]
    if candi:
        red.remove(sorted(candi, key=lambda x: x[1], reverse=True)[0])
        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)]

R.sort(key=lambda x: -x[1])
B.sort(key=lambda x: x[0])

idx = 0
ans = 0
for xr, yr in R:
    for xb, yb in B:
        if xr < xb and yr < yb:
            ans += 1
            B.remove([xb, yb])
            break
            
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
Y = [list(map(int, input().split())) for _ in range(N)]
X.sort(key=lambda x:x[1], reverse=True)
Y.sort()
ans = 0
xf = [0] * N
yf = [0] * N
C = []
i = 0
while i < N:
    if yf[i] == 1:
        i+= 1
        continue
    for j in range(N):
        if xf[j] == 0:
            if Y[i][0] > X[j][0] and Y[i][1] > X[j][1]:
                ans += 1
                xf[j] = 1
                yf[i] = 1
                i = 0
                break

    i += 1
print(ans)

Submission status: Accepted

Solution code:
import queue

class Dinic():
    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())
AB = [list(map(int,input().split())) for i in range(N)]
CD = [list(map(int,input().split())) for i in range(N)]

MF = Dinic(2*N+2) ## 二部グラフの2*N点と、始点と終点の2点

## 赤と青を結ぶ
for i in range(N):
  for j in range(N):
    if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
      MF.add_edge(i, j+N, 1) ## 今回は重み1
      
## 始点と赤を結ぶ
for i in range(N):
  MF.add_edge(2*N, i, 1)
  
## 青と終点を結ぶ
for j in range(N):
  MF.add_edge(j+N, 2*N+1, 1) ## 順番に注意: 青がfrom、終点がto
  
max_flow = MF.max_flow(2*N, 2*N+1)
print(max_flow)

Submission status: Accepted

Solution code:
N = int(input())

rs, bs = [], []  # (x, y, pair_flag)

for _ in range(N):
    rs.append(list(map(int, input().split())) + [0])

for _ in range(N):
    bs.append(list(map(int, input().split())) + [0])

rs.sort(key=lambda x: x[1])
bs.sort()

npair = 0
ir, ib = 0, 0
while ib < N:
    bx, by, _ = bs[ib]
    ir = N-1
    while ir >= 0:
        rx, ry, paired = rs[ir]
        if not paired and rx < bx and ry < by:
            rs[ir][2] = bs[ib][2] = 1
            npair += 1
            break
        ir -= 1
    ib += 1

print(npair)

Submission status: Accepted

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    red = sorted([[a[i],b[i]] for i in range(N)], key=lambda x:x[1], reverse=True)
    blue = sorted([[c[i],d[i]] for i in range(N)], key=lambda x:x[0])

    checked = [False] * N
    

    for i in range(N):
        for j in range(N):
            if((red[j][0] < blue[i][0] and red[j][1] < blue[i][1]) and  not checked[j]):
                checked[j] = True
                break

    print(checked.count(True))

        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ARC 092 C 最大マッチング問題


class Edge(object):

    def __init__(self, src, dst, cap):
        self.src = src
        self.dst = dst
        self.cap = cap
        self.rev = None

    def create_rev(self):
        """
        対応する残余グラフの辺を作成して返す。
        本来の辺と残余グラフの辺は相互に参照を持ち合うため、このメソッド以外から生成しないこと。
        """
        rev = Edge(self.dst, self.src, 0)
        self.rev = rev
        rev.rev = self
        return rev


class FordFulkerson:

    def __init__(self, N):
        self.N = N
        self.G = [list() for _ in range(N)]  # G[i]: 頂点iに接続している全ての有向辺のリスト

    def add_edge(self, src, dst, cap):
        forward = Edge(src, dst, cap)
        backward = forward.create_rev()
        self.G[src].append(forward)
        self.G[dst].append(backward)

    def flow(self, src, dst):
        max_flow = 0
        while True:
            self.used = [0] * self.N
            flow = self._dfs(src, dst)
            if flow == 0:  # f=0 が返るのは全てのパスを走査してこれ以上検討するパスがなくなったタイミング
                break
            max_flow += flow
        return max_flow

    def _dfs(self, v, t, f=float('inf')):
        """
        深さ優先でグラフを走査し、目的地に達するパスがあるか検索する。
        パスが存在すればその時の最大流を返し、存在しなければ0を返す。
        最大流量がFである時、高々F回のDFSをすることになるため、 O(F|E|) となる。

        :param v: 始点のインデックス
        :param t: 終点のインデックス
        :param f: 現在の再帰スタックにおける暫定の最大流
        """
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.G[v]:
            if e.cap and not used[e.dst]:
                d = self._dfs(e.dst, t, min(f, e.cap))
                if d:
                    e.cap -= d
                    e.rev.cap += d
                    return d
        return 0


N = int(input())
reds = [tuple(map(int, input().split())) for _ in range(N)]
blues = [tuple(map(int, input().split())) for _ in range(N)]

# 0: s
# 1 to N: reds
# N + 1 to 2N: blues
# 2N + 1: t
ff = FordFulkerson(2 * N + 2)
for i in range(N):
    r_x, r_y = reds[i]
    r_idx = i + 1
    ff.add_edge(0, r_idx, 1)  # sから赤の各点への辺
    for j in range(N):
        b_x, b_y = blues[j]
        b_idx = j + N + 1
        if r_x < b_x and r_y < b_y:
            ff.add_edge(r_idx, b_idx, 1)  # 赤の各点から青の各点への辺
for i in range(N + 1, 2 * N + 1):
    ff.add_edge(i, 2 * N + 1, 1)  # 青の各点からtへの辺

# 最大流 = 最大マッチング数
print(ff.flow(0, 2 * N + 1))

Submission status: Accepted

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


ans = 0

red_candidate = []
flag = False
for i in blue:
    red_candidate = []
    for j in range(len(red)):
        if i[0] <= red[j][0]:
            break
        else:
            if red[j][1] < i[1]:
                red_candidate.append([red[j][1], j])
                flag = True

    tmp_red_ymax_index = 0
    red_candidate = sorted(red_candidate, key=lambda x: -x[0])

    if flag:
       del  red[red_candidate[0][1]] 
       ans += 1
       flag = False
print(ans)

Submission status: Accepted

Solution code:

def findpath(v, t, edges, flow, visited):
    visited.add(v)
    for u in edges[v]:
        if u in visited:
            continue
        if flow[(v, u)] == 1:
            continue
        if u == t:
            return [v, t]
        path = findpath(u, t, edges, flow, visited)
        if path:
            return [v] + path
    return None

def max_match(R, B, edges):
    s, t = 'S', 'T'
    flow = {}
    for b in B:
        flow[(b, t)] = 0
        edges[b].append(t)  # add edge b -> t

    for r in R:
        flow[(s, r)] = 0
        for b in edges[r]:
            flow[(r, b)] = 0
            flow[(b, r)] = 1

    for r in R:
        if flow[(s, r)] == 1:
            continue
        path = findpath(r, t, edges, flow, set())
        if not path:
            continue
        path = [s] + path
        for u, v in zip(path, path[1:]):
            flow[(u, v)] = 1
            flow[(v, u)] = 0
    return flow

def solve(R, B, edges):
    flow = max_match(R, B, edges)
    match = 0
    for r in R:
        for b in edges[r]:
            match += flow[(r, b)]
    return match

N = int(input())
R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]
edges = {r:[] for r in R+B}

for r in R:
    rx, ry = r
    for b in B:
        bx, by = b
        if rx < bx and ry < by:
            edges[r].append(b)
            edges[b].append(r)

print(solve(R, B, edges))

Submission status: Accepted

Solution code:
label = {}
flow = {}
s, t = 'S', 'T'

def printpath(path):
    return
    for u, v in zip(path, path[1:]):
        print("%s -%d-> " % (label[u], flow[(u,v)]), end="")
    print("")

def printflow():
    return
    print("--flow--")
    for r in R:
        for b in edges[r]:
            print("  ", label[r], label[b], "s->r=%d"%flow[(s, r)], ", r->b=%d"%flow[(r, b)], ", b->t=%d"%flow[(b, t)])
            #print("  ", label[r], label[b], "r->s=%d"%flow[(r, s)], ", b->r=%d"%flow[(b, r)], ", t->b=%d"%flow[(t, b)])
        if edges[r]:
            print()

def findpath(v, t, edges, flow, visited):
    visited.add(v)
    #print(label[v], edges[v])
    for u in edges[v]:
        if u in visited:
            continue
        if flow[(v, u)] == 1:
            continue
        if u == t:
            return [v, t]
        path = findpath(u, t, edges, flow, visited)
        if path:
            return [v] + path
    return None

def max_match(R, B, edges):

    # init edge b - t
    for b in B:
        flow[(b, t)] = 0
        flow[(t, b)] = 1
        edges[b].append(t)

    edges[s] = []
    # init edge s - r
    for r in R:
        flow[(s, r)] = 0
        flow[(r, s)] = 1
        edges[s].append(r)

        # init flow r - b
        for b in edges[r]:
            flow[(r, b)] = 0
            flow[(b, r)] = 1

    change = True
    while change:
        printflow()
        change = False
        for r in R:
            if flow[(s, r)] == 1:
                continue
            path = findpath(r, t, edges, flow, set([s]))
            if not path:
                continue
            #printpath(path)
            path = [s] + path
            for u, v in zip(path, path[1:]):
                flow[(u, v)] = 1
                flow[(v, u)] = 0
            #change = True
    printflow()
    return flow

def solve(R, B, edges):
    flow = max_match(R, B, edges)

    match = 0
    for r in R:
        for b in edges[r]:
            match += flow[(r, b)]
    return match
            

N = int(input())

R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]
for i, r in enumerate(R):
    label[r] = "R%d" % (i+1)
    #print(label[r], r)
for i, r in enumerate(B):
    label[r] = "B%d" % (i+1)
    #print(label[r], r)
label[s] = 'S'
label[t] = 'T'

edges = {}
for r in R:
    edges[r] = []
for b in B:
    edges[b] = []

for r in R:
    rx, ry = r
    for b in B:
        bx, by = b
        if rx < bx and ry < by:
            edges[r].append(b)
            edges[b].append(r)


print(solve(R, B, edges))

Submission status: Accepted

Solution code:
label = {}
flow = {}
s, t = 'S', 'T'

def printpath(path):
    return
    for u, v in zip(path, path[1:]):
        print("%s -%d-> " % (label[u], flow[(u,v)]), end="")
    print("")

def printflow():
    return
    print("--flow--")
    for r in R:
        for b in edges[r]:
            print("  ", label[r], label[b], "s->r=%d"%flow[(s, r)], ", r->b=%d"%flow[(r, b)], ", b->t=%d"%flow[(b, t)])
            #print("  ", label[r], label[b], "r->s=%d"%flow[(r, s)], ", b->r=%d"%flow[(b, r)], ", t->b=%d"%flow[(t, b)])
        if edges[r]:
            print()

def findpath(v, t, edges, flow, visited):
    visited.add(v)
    #print(label[v], edges[v])
    for u in edges[v]:
        if u in visited:
            continue
        if flow[(v, u)] == 1:
            continue
        if u == t:
            return [v, t]
        path = findpath(u, t, edges, flow, visited)
        if path:
            return [v] + path
    return None

def max_match(R, B, edges):

    # init edge b - t
    for b in B:
        flow[(b, t)] = 0
        flow[(t, b)] = 1
        edges[b].append(t)

    edges[s] = []
    # init edge s - r
    for r in R:
        flow[(s, r)] = 0
        flow[(r, s)] = 1
        edges[s].append(r)

        # init flow r - b
        for b in edges[r]:
            flow[(r, b)] = 0
            flow[(b, r)] = 1

    change = True
    while change:
        printflow()
        change = False
        for r in R:
            if flow[(s, r)] == 1:
                continue
            path = findpath(r, t, edges, flow, set([s]))
            if not path:
                continue
            #printpath(path)
            path = [s] + path
            for u, v in zip(path, path[1:]):
                flow[(u, v)] = 1
                flow[(v, u)] = 0
            change = True
    printflow()
    return flow

def solve(R, B, edges):
    flow = max_match(R, B, edges)

    match = 0
    for r in R:
        for b in edges[r]:
            match += flow[(r, b)]
    return match
            

N = int(input())

R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]
for i, r in enumerate(R):
    label[r] = "R%d" % (i+1)
    #print(label[r], r)
for i, r in enumerate(B):
    label[r] = "B%d" % (i+1)
    #print(label[r], r)
label[s] = 'S'
label[t] = 'T'

edges = {}
for r in R:
    edges[r] = []
for b in B:
    edges[b] = []

for r in R:
    rx, ry = r
    for b in B:
        bx, by = b
        if rx < bx and ry < by:
            edges[r].append(b)
            edges[b].append(r)


print(solve(R, B, edges))

Submission status: Accepted

Solution code:
from collections import defaultdict

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()
cnt = 0

for b in blue:
    max_r_y = -1
    paired = (-1, -1)
    for r in red:
        if r[0] > b[0]:
            break
        if max_r_y < r[1] < b[1]:
            max_r_y = r[1]
            paired = r

    if paired != (-1, -1):
        red.remove(paired)
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
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)]
B_ = B[:]

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

for i, b in enumerate(B):
    matchR = [(j, r) for j, r in enumerate(R) if r[0] < b[0] and r[1] < b[1]]
    if matchR:
        matchR.sort(key=lambda x: x[1][1], reverse=True)
        del R[matchR[0][0]]
    else:
        B_[i] = None

print(len([b for b in B_ if b is not None]))

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

ans = 0

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


for c,d in cd:
    for i,(a,b) in enumerate(ab):
        if a < c and b < d:
            ans +=1 
            ab.pop(i)
            break
print(ans)

Submission status: Accepted

Solution code:
dat_r = []
dat_b = []

n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    dat_r.append((a, b))

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

dat_r.sort(key=lambda x: ( -x[1], -x[0]-x[1]))
dat_b.sort(key=lambda x: ( +x[0],  x[0]+x[1]))
#print("")
#print(dat_r)
#print(dat_b)
res = 0
"""
for i in range(n):
    for j in range(len(dat_b)):
        # print("{0} < {1} vs {2} < {3}".format(dat_r[i][0] ,dat_b[j][0] ,dat_r[i][1] ,dat_b[j][1]))
        if dat_r[i][0] < dat_b[j][0] and dat_r[i][1] < dat_b[j][1]:
            # print("ok")
            res += 1
            dat_b  = dat_b[0:j] + dat_b[j + 1:]
            break
print(res)
"""
for i in range(n):
    for j in range(len(dat_r)):
        #print("{0} < {1} vs {2} < {3}".format(dat_r[i][0] ,dat_b[j][0] ,dat_r[i][1] ,dat_b[j][1]))
        if dat_r[j][0] < dat_b[i][0] and dat_r[j][1] < dat_b[i][1]:
            #print("ok")
            res += 1
            dat_r  = dat_r[0:j] + dat_r[j + 1:]
            break
print(res)

Submission status: Accepted

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

B = sorted(B, key=lambda p: p[0])

ans = 0
for bx, by in B:
    ry_max = -1
    idx = -1
    for i, (rx, ry) in enumerate(R):
        if rx < bx and ry < by and ry_max < ry:
            ry_max = ry
            idx = i
    if idx != -1:
        R.pop(idx)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
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 x: x[1])
blue.sort()
ans = 0
for i in range(n):
    a = 0
    for j in range(len(red)):
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
            a = j
    if blue[i][0] > red[a][0] and blue[i][1] > red[a][1]:
        ans += 1
        del red[a]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = [[int(i) for i in input().split()] for _ in range(N)]
B = [[int(i) for i in input().split()] for _ in range(N)]

R.sort()
B.sort()

count = 0
tmp = []
for bx, by in B:
    for rx, ry in R:
        if bx > rx and by > ry:
            tmp.append([rx, ry])
    if tmp != []:
        max_red = max(tmp, key=lambda r: r[1])
        count += 1
        R.remove(max_red)
        tmp = []
print(count)

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(key=lambda x: x[1])
blue.sort(key=lambda x: x[0])
ans = 0
for b in blue:
    for r in red:
        if r[0] <= b[0] and r[1] <= b[1]:
            ans += 1
            red.remove(r)
            break
print(ans)

Submission status: Accepted

Solution code:
import copy
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))
ab.sort(key=lambda x :x[1],reverse=True)#abをy座標で逆ソート
#ab.sort(key=lambda x :x[0])#abをx座標でソート
cd.sort(key=lambda x :x[0])#cdをx座標でソート
ans=0
for c,d in cd:#あるc,dに対して、適切なabを探しともに消去する
    for a,b in ab:#
        if b<d and a<c:
            ab[ab.index([a,b])]=[1000,1000] #abは糞でかく、cdはクソ小さくする
            cd[cd.index([c,d])]=[-1000,-1000]
            ans+=1
            break#次のc,dを見に行く
print(ans)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
x=sorted(zip(t[1:n*2:2],t[:n*2:2]))
y=sorted(zip(t[n*2::2],t[n*2+1::2]))[::-1]
c=0
while y:
  i,j=y.pop()
  k=len(x)-1
  while k>=0:
    b,a=x[k]
    if a<i and b<j:
      c+=1
      del x[k]
      break
    k-=1
print(c)

Submission status: Accepted

Solution code:
N=int(input())
ab=[]
for i in range(N):
    a,b=map(int,input().split())
    ab.append([b,a])
cd=[]
for i in range(N):
    c,d=map(int,input().split())
    cd.append([c,d])
cd.sort(key=lambda x:(x[0],x[1]))
ab.sort(key=lambda x:(-x[0],-x[1]))
ans=0
for i in cd:
    c,d=i[0],i[1]
    for j in ab:
        b,a=j[0],j[1]
        if a<c and b<d :
            ans+=1
            ab.remove([b,a])
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
AB = [[0]+list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]
from operator import itemgetter

points = AB.copy()
for c,d in CD:
    points.append([1,c,max(0,d-0.1)])
points.sort(key = itemgetter(2))

ans = 0
record = [0]*(2*n+1)
for flag, x, y in points:
    if flag:
        for i in range(x-1,-1,-1):
            if record[i] > 0:
                ans += 1
                record[i] -= 1
                break
    else:
        record[x] += 1
print(ans)

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

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

print(ans)

Submission status: Accepted

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

c = 0

for b in blue:
    for r in red:
        if r[0] < b[0] and r[1] < b[1]:
            c += 1
            red.remove(r)
            break
    
print(c)

Submission status: Accepted

Solution code:
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)]

ans = 0
r,b = sorted(r, key=lambda x:x[1],reverse=True), sorted(b)
for i in b:
    for j in r:
        if i[1]>j[1] and i[0] >j[0]:
            ans += 1
            r.remove(j)
            break
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lia= [ [ int(it) for it in input().split() ] for i in range(N)]
lib= [ [ int(it) for it in input().split() ] for i in range(N)]

# Hopcroft-Karp Algorithm
from collections import deque
class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        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)
        self.level = level
        return level[1] is not None

    def dfs(self, v, t):
        if v == t:
            return 1
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w] and self.dfs(w, t):
                e[1] = 0
                rev[1] = 1
                return 1
        return 0

    def flow(self):
        flow = 0
        G = self.G
        bfs = self.bfs; dfs = self.dfs
        while bfs():
            *self.it, = map(iter, G)
            while dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]
    
hop = HopcroftKarp(N,N)

for i in range(N):
  a,b = lia[i]
  for j in range(N):
    c,d = lib[j]
    if ( a<c and b<d ):
      hop.add_edge(i,j)
co = hop.flow()
print ( co )

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)]
r=sorted(r,key=lambda x:x[0]*2*n+x[1])
b=sorted(b,key=lambda x:x[0]*2*n-x[1])
cnt=0
i=0
while i!=n:
    t=[0,0]
    for x,y in r:
        if x<b[i][0] and y<b[i][1] and t[1]<=y:
            t=[x,y]
    if t in r:
        r.remove(t)
        cnt+=1
    i+=1
print(cnt)

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


def main():
    n = intin()
    ablist = intinl(n)
    cdlist = intinl(n)

    ablist.sort()
    cdlist.sort()
    ans = 0

    while ablist:
        a, b = ablist.pop()
        idx = binl(cdlist, (a, b))

        cand = None
        for i, (c, d) in enumerate(cdlist[idx:]):
            if b < d:
                if cand is None:
                    cand = (i, c, d)
                else:
                    ci, cc, cd = cand
                    if d < cd:
                        cand = (i, c, d)

        if cand is None:
            continue

        ci, cc, cd = cand
        del cdlist[idx + ci]
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()