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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(4100000)

def augment(g, src, matchTo, visited):
    if src < 0:
        return True
    for dst in g.get(src, []):
        if not visited[dst]:
            visited[dst] = True
            if augment(g, matchTo[dst], matchTo, visited):
                matchTo[src] = dst
                matchTo[dst] = src
                return True
    return False


def match(g, L):
    n = len(g)
    matchTo = [-1] * n
    m = 0
    for src in range(L):
        visited = [False] * n
        if augment(g, src, matchTo, visited):
            m += 1
    return m


def solve(N, a, b, c, d):
    g = dict()
    for i in range(2*N):
        g[i] = []
    for i in range(N):
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                g[i].append(N+j)
                g[N+j].append(i)
    print(match(g, N))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    a = [int()] * (N)
    b = [int()] * (N)
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (N)
    d = [int()] * (N)
    for i in range(N):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    Red = []
    Blue = []
    for i in range(N):
        a, b = map(int, input().split())
        Red.append([b,a])
    for i in range(N):
        c, d = map(int, input().split())
        Blue.append([c,d])

    Red.sort(reverse=True)
    Blue.sort()
    ans = 0
    for x, y in Blue:
        for v, u in Red:
            if x > u and y > v:
                ans += 1
                Red.remove([v,u])
                break
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue

# http://vartkw.hatenablog.com/entry/2016/12/02/002703


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

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)


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

dinic = Dinic(2*N+2)
for i in range(N):
    dinic.add_edge(0, i+1, 1)
    dinic.add_edge(N+i+1, 2*N+1, 1)
for i in range(N):
    for j in range(N):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            dinic.add_edge(i+1, N+j+1, 1)

print(dinic.max_flow(0, 2*N+1))

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)]
cd.sort()
count=0
for i in range(n):
    c,d=cd[i]
    m=-1
    memo=-1
    for j in range(len(ab)):
        a,b=ab[j]
        if a<c and m<b<d:
            memo=j
            m=b
    if memo!=-1:
        ab.pop(memo)
        count+=1
print(count)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

# Dinic's algorithm
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

#無向グラフ？
#    def add_multi_edge(self, v1, v2, cap1, cap2):
#        edge1 = [v2, cap1, None]
#        edge1[2] = edge2 = [v1, cap2, edge1]
#        self.G[v1].append(edge1)
#        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

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

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

#処理内容
def main():
	N = int(input())
	A = []
	B = []
	for i in range(N):
		a, b = getlist()
		A.append([a, b])
	for i in range(N):
		c, d = getlist()
		B.append([c, d])

	G = Dinic(2 * N + 2)
	for i in range(N):
		G.add_edge(0, i + 1, 1)
		G.add_edge(N + 1 + i, 2 * N + 1, 1)
	for i in range(N):
		for j in range(N):
			if A[i][0] < B[j][0] and A[i][1] < B[j][1]:
				G.add_edge(i + 1, N + 1 + j, 1)
	print(G.flow(0, 2 * N + 1))


if __name__ == '__main__':
	main()

Submission status: Accepted

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

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 = sorted(red, key=itemgetter(0), reverse=True)
    blue = sorted(blue, key=itemgetter(1))
    visited = [False] * N
    ans = 0
    for i in blue:
        c = i[0]
        d = i[1]
        for j in range(N):
            a = red[j][0]
            b = red[j][1]
            if a < c and b < d and not visited[j]:
                ans += 1
                visited[j] = True
                break
    print(ans)


if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
import heapq

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()
B.sort()

# 青い点をx座標が小さい順にみていき、
# ペアにできる赤い点のうちy座標が最も大きいものをペアとする。
ans = 0
RS = [False for _ in range(N)]
for bx,by in B:
  pair = []
  for i in range(N):
    rx,ry = R[i]
    if rx > bx:
      break
    if ry > by or RS[i]:
      continue
    heapq.heappush(pair,[-ry,i])
  if len(pair) > 0:
    _,idx = heapq.heappop(pair)
    RS[idx] = True
    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(key=lambda x: x[0])
R.sort(key=lambda x: x[0])

res = 0
for b in B:

    targets = []
    for i in range(len(R)):
        r = R[i]
        if r[0] < b[0] and r[1] < b[1]:
            targets.append(r)
        if r[0] >= b[0]:
            break

    if len(targets) == 0:
        continue
    targets.sort(key=lambda x: x[1], reverse=True)
    R.remove(targets[0])
    res += 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
rls = []
rlog = [0]*N
bls = []
blog = [0]*N
for i in range(N):
  a, b = map(int, input().split())
  rls += [(a,b)]
for i in range(N):
  a, b = map(int, input().split())
  bls += [(a,b)]

bls.sort(key=lambda x:x[0])
ans = 0
for i in range(N):
  c, d = bls[i]
  mb = -1
  mj = 0
  for j in range(N):
    a, b = rls[j]
    if a<c and b<d and rlog[j]==0:
      if mb<b:
        mb = b
        mj = j
  if mb!=-1:
    rlog[mj] = 1
    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 = sorted(R, key=lambda x: -x[1])  # 赤い点はy座標が大きい順にする
B = sorted(B, key=lambda x: x[0])  # 青い点はx座標が小さい順にする

for a, b in B:  # 青い点, x座標が小さい順になっている
    for c, d in R:  # 赤い点, y座標が大きい順になっている
        if a > c and b > d:  # 青い点のx座標より赤い点のx座標が小さく, 青い点のy座標より赤い点のy座標が小さければペアにする
            R.remove([c, d])
            break

print(N - len(R))

Submission status: Accepted

Solution code:
N = int(input())
ab = []
for i in range(N):
    _a, _b = map(int, input().split())
    ab.append((_a, _b))
cd = []
for j in range(N):
    _c, _d = map(int, input().split())
    cd.append((_c, _d))
cd.sort()

s = set()
for j in range(N):
    maxb = -1
    maxi = -1
    for i in range(N):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1] and i not in s:
            if ab[i][1] > maxb:
                maxb = ab[i][1]
                maxi = i
    if maxi != -1:
        s.add(maxi)
print(len(s))

Submission status: Accepted

Solution code:
n=int(input())

red={}
for _ in range(n):
  x,y=map(int,input().split())
  if x in red:
    red[x].append(y)
  else:
    red[x]=[y]
  
blue={}
for _ in range(n):
  x,y=map(int,input().split())
  if x in blue:
    blue[x].append(y)
  else:
    blue[x]=[y]
#print(red,blue)
blueOption=[2*n+1,[]]

cnt=0
for i in range(2*n+1):
  border=2*n-i
  blueOption[0]=border
  if border in blue:
    blueOption[1]+=blue[border]
    blueOption[1].sort()
  #print(redOption))
  
  if border in red:
    redTemp=red[border]
    #print(border,redTemp)
    redTemp.sort(reverse=True)
    for item in redTemp:
      for blueItem in blueOption[1]:
        if item<blueItem:
          cnt+=1
          blueOption[1].remove(blueItem)
          break
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
ab = [[0, 0] for i in range(N)]
b = [0]*N
cd = [[0, 0] for i in range(N)]
d = [0]*N

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

points = [[] for i in range(N)]
points2 = [[] for i in range(N)]
cd.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)

points.sort(key=lambda x: len(x))
ans = 0

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    red = []
    for _ in range(N):
        a, b = map(int, input().split())
        red.append([a, b, 0])

    blue = []
    for _ in range(N):
        a, b = map(int, input().split())
        blue.append([a, b, 1])

    rb = red + blue
    rb.sort(key = lambda x: x[0])
    # print(rb)

    used = set()
    count = 0
    for i in range(2*N):
        if rb[i][2] == 1:
            min_j = None
            max_y = -1
            for j in range(i):
                if rb[j][2] == 0 and j not in used:
                    if max_y < rb[j][1] < rb[i][1]:
                        max_y = rb[j][1]
                        min_j = j
            if min_j != None:
                # print(i, min_j)
                used.add(min_j)
                count += 1
    return count

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

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
AB = sorted([list(map(int,input().split())) for i in range(N)])
CD = sorted([list(map(int,input().split())) for i in range(N)])
inf = float('inf')
ans = 0

for bx, by in CD:
    S = list(filter(lambda n:n[0]<bx, AB))
    S = list(filter(lambda n:n[1]<by, S))
    if len(S) != 0:
        S.sort(key=itemgetter(1))
        AB[AB.index(S[-1])] = [inf, inf]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ABC091C - 2D Plane 2N Points (ARC092C)
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = sorted(
        [tuple(map(int, input().split())) for _ in range(N)],
        key=lambda x: x[1],
        reverse=1,
    )
    B = sorted([tuple(map(int, input().split())) for _ in range(N)])
    ans, memo = 0, set()
    for bx, by in B:
        for i, (ax, ay) in enumerate(A):
            if i not in memo and ax < bx and ay < by:
                ans += 1
                memo |= {i}
                break
    print(ans)


if __name__ == "__main__":
    main()

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 val:val[1], reverse=True)
b.sort()

ans = 0

for bb in b:
    for i in range(N):
        if bb[0] > r[i][0] and bb[1] > r[i][1]:
            ans += 1
            N -= 1
            r.pop(i)
            break

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

inf = float('inf')


class Dinic(object):
    def __init__(self):
        self.V = set()
        self.adj = defaultdict(list)
        self.c = defaultdict(lambda: 0)
        self.f = defaultdict(lambda: 0)
        self.iter = defaultdict(lambda: 0)
    
    def add_edge(self, u, v, cap):
        self.V.add(u)
        self.V.add(v)
        self.adj[u].append(v)
        self.adj[v].append(u)
        self.c[(u, v)] = cap
    
    def bfs(self, s):
        self.level = {v: inf for v in self.V}
        self.level[s] = 0
        Q = deque([s])
        while len(Q) > 0:
            u = Q.popleft()
            for v in self.adj[u]:
                if self.c[(u, v)] <= 0:
                    continue
                if self.level[v] <= self.level[u]:
                    continue
                self.level[v] = self.level[u] + 1
                Q.append(v)
    
    def dfs(self, u, t, mincap):
        if u == t:
            return mincap

        for i in range(self.iter[u], len(self.adj[u])):
            self.iter[u] = i
            v = self.adj[u][i]
            if self.c[(u, v)] <= 0:
                continue
            if self.level[v] <= self.level[u]:
                continue
            d = self.dfs(v, t, min(mincap, self.c[(u, v)]))
            if d > 0:
                self.c[(u, v)] -= d
                self.c[(v, u)] += d
                return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        
        while True:
            self.bfs(s)

            if self.level[t] == inf:
                return flow
        
            self.iter = defaultdict(lambda: 0)
            d = self.dfs(s, t, inf)
            while d > 0:
                flow += d
                d = self.dfs(s, t, inf)


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    G = Dinic()
    for xr, yr in zip(a, b):
        G.add_edge(0, (xr, yr), 1)
        for xb, yb in zip(c, d):
            if xr < xb and yr < yb:
                G.add_edge((xr, yr), (xb, yb), 1)
    for xb, yb in zip(c, d):
        G.add_edge((xb, yb), 1, 1)
    print(G.max_flow(0, 1))
    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:
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])

N = int(input())

R = []
for _ in range(N):
    x, y = map(int, input().split())
    R.append(Point(x, y))

B = []
for _ in range(N):
    x, y = map(int, input().split())
    B.append(Point(x, y))

E = [[] for _ in range(N)]
for i, r in enumerate(R):
    for j, b in enumerate(B):
        if r.x < b.x and r.y < b.y:
            E[i].append(j)


class BipartiteMatching:
    def __init__(self, max_u: int, edges):
        self.max_u = max_u
        self.edges = edges  # u->vの隣接行列
        self.__match = None

    def dfs(self, v: int, visited: set) -> bool:
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)

            if self.__match[u] == -1 or self.dfs(self.__match[u], visited):
                self.__match[u] = v
                return True
        return False

    def execute(self):
        self.__match = [-1 for _ in range(self.max_u)]
        return sum(self.dfs(u, set()) for u in range(self.max_u))


print(BipartiteMatching(N, E).execute())

Submission status: Accepted

Solution code:
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
# Edge = namedtuple('Edge', ['from', 'to'])

N = int(input())

R = []
for _ in range(N):
    x, y = map(int, input().split())
    R.append(Point(x, y))

B = []
for _ in range(N):
    x, y = map(int, input().split())
    B.append(Point(x, y))

E = [[] for _ in range(N)]
for i, r in enumerate(R):
    for j, b in enumerate(B):
        if r.x < b.x and r.y < b.y:
            E[i].append(j)

match = [-1 for _ in range(N)]


def dfs(v: int, visited: set) -> bool:
    for u in E[v]:
        if u in visited:
            continue
        visited.add(u)

        if match[u] == -1 or dfs(match[u], visited):
            match[u] = v
            return True
    return False


def bipartite_matching():
    return sum(dfs(i, set()) for i in range(N))


print(bipartite_matching())

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

#print(R)
ans = 0
for bx,by in B:
 #   print(bx,by)
    for i in range(len(R)):
        if R[i][0] < bx and R[i][1] < by:
  #          print(R[i],"とマッチ")
            del R[i]
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
def can_match(x1, y1, x2, y2):
    return x1 < x2 and y1 < y2

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

for i in range(N):
    x, y = map(int, input().split())
    blue.append((x, y))
    
red.sort()
ans = 0
for i in range(N - 1, -1, - 1):
    xr, yr = red[i]
    yb_min = 2 * N
    arg_yb_min = 0
    matched = False
    for xb, yb in blue:
        if can_match(xr, yr, xb, yb) and yb < yb_min:
            matched = True
            arg_yb_min = xb
            yb_min = yb
    
    if matched:
        ans += 1
        blue.remove((arg_yb_min, yb_min))

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from operator import itemgetter

n = ni()
ab = [tuple(li()) for i in range(n)]
cd = [tuple(li()) for i in range(n)]

ab.sort(key=itemgetter(0), reverse=True)
cd.sort(key=itemgetter(1))

cd_used = [False]*n

ans = 0
for ai, bi in ab:
    for j, (cj, dj) in enumerate(cd):
        if ai < cj and bi < dj and (not cd_used[j]):
            cd_used[j] = True
            ans += 1

            break

print(ans)

Submission status: Accepted

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

L1 = sorted(L1,key=lambda x: x[1],reverse=True)
L2 = sorted(L2,key=lambda x: x[0],reverse=False)

ans = 0

checked = [0 for i in range(N)]

for i in range(N) :
    c,d = L2[i]
    for j in range(N) :
        a,b = L1[j]
        
        if a < c and b < d :
            if checked[j] :
                continue
            ans += 1
            checked[j] = 1
            break

print(ans)

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,i))
for i in range(N):
    a,b=map(int,input().split())
    blue.append((a,b,N+i))
from collections import defaultdict
branch=defaultdict(set)
for x in red:
    for y in blue:
        if x[0]<y[0] and x[1]<y[1]:
            branch[x[2]]|={y[2]}
            branch[y[2]]|={x[2]}
def main(i):
    global used
    global branch
    global match
    if i in used:
        return False
    for nex in branch[i]:
        if nex in used:
            continue
        elif match[nex]==-1:
            match[nex]=i
            match[i]=nex
            return True
        else:
            used|={i}
            if main(match[nex]):
                match[i]=nex
                match[nex]=i
                return True
    return False
match=[-1]*(2*N)
for i in range(2*N):
    used=set()
    if match[i]==-1:
        main(i)
print(sum([1 for i in range(2*N) if match[i]>=0])//2)

Submission status: Accepted

Solution code:
import copy
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])
######
INF = 10**10
R.sort(key=lambda x:-x[1])
B.sort(key=lambda x:x[0])
ans = 0
for r in range(N):
    for b in range(N):
        if R[r][0]<B[b][0] and R[r][1]<B[b][1]:
            ans+=1
            B[b][0]=-INF
            B[b][1]=-INF
            break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
R=sorted([list(map(int,input().split())) for i in range(N)])
B=sorted([list(map(int,input().split())) for i in range(N)])
ans=0
for i in range(N):
    a=[-1,-1]
    x=-1
    for j in range(len(R)):
        if B[i][0]>R[j][0] and B[i][1]>R[j][1]:
            if a[1]<R[j][1]:
                a=R[j]
                x=j
    if x>=0:
        del R[x]
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
cd = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[1], reverse=True)
cd.sort(key=lambda x: x[0])
ans = 0

for i in cd:
    j = 0
    for j in range(len(ab)):
        if ab[j][0] < i[0] and ab[j][1] < i[1]:
            ab.pop(j)
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
red=[tuple(map(int,input().split())) for i in range(N)]
blue=[tuple(map(int,input().split())) for j in range(N)]
from collections import defaultdict
branch=defaultdict(set)
for i,r in enumerate(red):
    for j,b in enumerate(blue):
        if r[0]<b[0] and r[1]<b[1]:
            branch[r[0]]|={b[0]}
            branch[b[0]]|={r[0]}
match=[-1]*(2*N)
used=[False]*(2*N)
def dfs(v):
    global used
    global match
    used[v]=True
    for nex in (branch[v]):
        w=match[nex]
        if (w<0 or (not used[w] and dfs(w))):
            match[nex]=v
            match[v]=nex
            return True
    return False
    
def main():
    global used
    global match
    cnt=0
    for i in range(2*N):
        if match[i]<0:
            used=[False]*(2*N)
            if dfs(i):
                cnt+=1
    return cnt
print(main())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
R = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
B = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
G = [[] for _ in range(2 * N + 2)]

def add_edge(f, to, cap):
    G[f].append([to, cap, len(G[to])])
    G[to].append([f, 0, len(G[f]) - 1])

# S -> R and B -> T
for i in range(N):
    add_edge(0, 1 + i, 1)
    add_edge(N + 1 + i, 2 * N + 1, 1)
    
# R -> B
for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1]:
            add_edge(1 + i, N + 1 + j, 1)

used = [False] * (2 * N + 2)
def dfs(v, t, f):
    if v == t: return f
    used[v] = True
    for i in range(len(G[v])):
        e_to, e_cap, e_rev = G[v][i]
        if used[e_to] == False and e_cap > 0:
            d = dfs(e_to, t, min(f, e_cap))
            if d > 0:
                G[v][i][1] -= d
                G[e_to][e_rev][1] += d
                return d
    return 0
    
def max_flow(s, t):
    global used
    flow = 0
    while True:
        used = [False] * (2 * N + 2)
        f = dfs(s, t, float('inf'))
        if f == 0: return flow
        flow += f
        
print(max_flow(0, 2 * N + 1))

Submission status: Accepted

Solution code:
N = int(input())
AB = [tuple([int(_) for _ in input().split()]) for i in range(N)]
CD = [tuple([int(_) for _ in input().split()]) for i in range(N)]

AB = sorted(AB, key=lambda x:x[1])
CD = sorted(CD, key=lambda x:x[0])

result = 0

for c, d in CD:
    xs = [x for x in AB if x[0] < c and x[1] < d]
    if xs:
        AB.remove(xs[-1])
        result += 1

print(result)

Submission status: Accepted

Solution code:
n=int(input())
p1=[list(map(int,input().split())) for _ in range(n)]
p2=[list(map(int,input().split())) for _ in range(n)]
p1=sorted(p1,key=lambda x:x[1])
p1=sorted(p1,key=lambda x:x[0])
p2=sorted(p2,key=lambda x:x[1])
p2=sorted(p2,key=lambda x:x[0])
ans=0
for i in range(n-1,-1,-1):
  pos=-1
  tmp=10**10
  for j in range(len(p2)-1,-1,-1):
    if p1[i][0]>=p2[j][0]:
      break
    else:
      if p1[i][1]<p2[j][1] and p2[j][1]<tmp:
        tmp=p2[j][1]
        pos=j
  if pos!=-1:
    ans+=1
    p2.pop(pos)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

class Dinic:
    def __init__(self, v, inf=float('inf')):
        self.V = v
        self.inf = inf
        # self.G = {i:[] for i in range(self.V)}
        self.G = [[] for _ in range(self.V)]
        self.level = [0] * self.V
        self.iter = [0] * self.V

    def add_edge(self, from_v, to_v, cap):
        self.G[from_v].append({'to': to_v, 'cap': cap, 'rev': len(self.G[to_v])})
        self.G[to_v].append({'to': from_v, 'cap': 0, 'rev': len(self.G[from_v]) - 1})

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        que = deque()
        que.appendleft(s)

        while len(que) > 0:
            v = que.pop()
            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.appendleft(e['to'])

    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 maxflow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow

            self.iter = [0] * self.V
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.inf)


def read_input():
    n = int(input())

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

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

    return n, red, blue


def submit():
    n, red, blue = read_input()
    dinic = Dinic(2*n+2)

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

    for i,b in enumerate(blue):
        for j,r in enumerate(red):
            if r[0] < b[0] and r[1] < b[1]:
                dinic.add_edge(j, n+i, 1)

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

if __name__ == '__main__':
    submit()

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()
ret =0
for c, d in blue:
    diff = 10 ** 5
    tmp = -1
    for i, (a, b) in enumerate(red):
        if c > a and d > b:
            if diff > d-b:
                diff = d - b
                tmp = i
    if tmp > -1:
        red[tmp] = [10**5, 10**5]
        ret += 1
print(ret)