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

Solution (Python):
n = int(input())  
red_li = [list(map(int, input().split())) for _ in range(n)]
blue_li = [list(map(int, input().split())) for _ in range(n)]
ans = 0
red_li.sort(reverse = True, key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[0], x[1]))

def count(red, blue):
    used_red = []
    used_blue = []
    for i in red:
        if i in used_red:
            continue
        for j in blue:
            if j in used_blue:
                continue
            if i[0] < j[0] and i[1] < j[1]:
                used_red.append(i)
                used_blue.append(j)
                break
    return len(used_red)


red_li.sort(reverse = True,key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
print(ans)

Solution (Python):
n = int(input())  
red_li = [list(map(int, input().split())) for _ in range(n)]
blue_li = [list(map(int, input().split())) for _ in range(n)]
ans = 0
red_li.sort(reverse = True, key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[0], x[1]))

def count(red, blue):
    used_red = []
    used_blue = []
    for i in red:
        if i in used_red:
            continue
        for j in blue:
            if j in used_blue:
                continue
            if i[0] < j[0] and i[1] < j[1]:
                used_red.append(i)
                used_blue.append(j)
                break
    return len(used_red)

ans = count(red_li, blue_li)
red_li.sort(reverse = True,key = lambda x : (x[1], x[0]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
red_li.sort(reverse = True,key = lambda x : (x[1], x[0]))
blue_li.sort( key = lambda x : (x[0], x[1]))
ans = max(ans, count(red_li, blue_li))
red_li.sort(reverse = True,key = lambda x : (x[0], x[1]))
blue_li.sort( key = lambda x : (x[1], x[0]))
ans = max(ans, count(red_li, blue_li))
print(ans)

Solution (Python):
N = int(input())
X = [list(map(int,input().split())) for i in range(2*N)]

Alist = []
Blist = []

for i in range(N):
	Alist.append(X[i]+[0])
	Blist.append(X[i+N])

Alist.sort(key=lambda Alist:[-Alist[1],Alist[0]])
Blist.sort(key=lambda Blist:[Blist[0],-Blist[1]])
ans = 0
j = 0
while j<N:
	i = 0
	while i < len(Alist):
		if (Alist[i][0]<Blist[j][0] and Alist[i][1]<Blist[j][1]):
			ans += 1
			del Alist[i]
			break
		i+=1
	j+=1

print(ans)

Solution (Python):
n=int(input())
a=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[-x[1],x[0]])
b=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])
c=0
i=j=0
while j<n:
    i=0
    while i<len(a):
        if a[i][0]<b[j][0] and a[i][1]<b[j][1]:
            c+=1
            del a[i]
            break
        i+=1
    j+=1
print(c)

Solution (Python):
import collections


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u]) - 1])
            self.edges[v].append([u, c, len(self.edges[u])])
            self.edges[u].append([v, 0, len(self.edges[v]) - 1])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = collections.deque([s])
        while que:
            v = que.popleft()
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += 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 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(N)]
graph = Dinic(2*N+2)
for i in range(1, N+1):
    graph.add(0, i, 1)

for i in range(N+1, 2*N+1):
    graph.add(i, 2*N+1, 1)

for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph.add(i+1, N+1+j, 1)

print(graph.maxFlow(0, 2*N+1))

Solution (Python):
from collections import defaultdict

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

for i in range(n):
    c, d = map(int, input().split())
    for index, p, q in rec:
        if p < c and q < d:
            G[index].append(i + n)
            G[i + n].append(index)

used = [False] * 2 * n
match = [-1] * 2 * n

def dfs(v):
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True



ma = 0
for i in range(n):
    if match[i] < 0:
        used = [False] * 2 * n
        if dfs(i):
            ma += 1

print(ma)

Solution (Python):
from functools import reduce
import math
from operator import itemgetter

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    ab = []
    cd = []
    for i in range(N):
        s1, s2 = (int(_) for _ in input().split())
        ab.append((s1,s2))
    for i in range(N):
        s1, s2 = (int(_) for _ in input().split())
        cd.append((s1,s2))
    cnt = 0
    ab = sorted(ab, key = itemgetter(0))
    cd = sorted(cd, key = itemgetter(0))
    for i in range(N):
        rp = -1
        tmp = -1
        for j in range(len(ab)):
            
            if ab[j][0]<cd[i][0] and ab[j][1]<cd[i][1]:
                if ab[j][1] > tmp:                    
                    tmp = ab[j][1]
                    rp = j
        if rp >=0:
            
            ab.pop(rp)
            cnt +=1
    print(cnt)
    
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
CD = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)
CD.sort()
ans = 0

for i, red in enumerate(AB):
    for j, blue in enumerate(CD):
        if red[0] < blue[0] and red[1] < blue[1]:
            ans += 1
            CD.pop(j)
            break
print(ans)

Solution (Python):
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)]
v=[]
r.sort()
b.sort()
count=0
 
for i in range(n):
    for j in range(len(r)):
        if b[i][0]<=r[j][0] or b[i][1]<=r[j][1]:
            pass
        else:
            v.append(r[j])    
    if v!=[]:
        v.sort(key=lambda x:x[1])
        v.reverse()
        r.remove(v[0])
        
            
        v=[]
        count+=1
print(count)

Solution (Python):
N = int(input())
AB = sorted((tuple(map(int,input().split())) for _ in [0]*N),key=lambda x:(x[0],-x[1]))
CD = sorted((tuple(map(int,input().split())) for _ in [0]*N),key=lambda x:(x[0],-x[1]))
ans = 0
for c,d in CD:
    m = max([b for a,b in AB if a<c and b<d]+[-1])
    if m==-1:continue
    for i,ab in enumerate(AB):
        a,b = ab
        if b == m:
            ans += 1
            AB[i] = (1000,1000)
            break
print(ans)

Solution (Python):
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
ans = 0
red = sorted(red, key = lambda x:x[1] * -1)
blue = sorted(blue)
for b in blue:
	for r in red:
		if b[0] > r[0] and b[1] > r[1]:
			ans += 1
			red.remove(r)
			break
print(ans)

Solution (Python):
N = int(input())

R = [(0, 0)] * N
for n in range(N):
  x, y = map(int, input().split())
  R[n] = (x, y)

B = [[0, 0]] * N
for n in range(N):
  x, y = map(int, input().split())
  B[n] = (x, y)

R = sorted(R, key=lambda x: (x[0], x[1]))
B = sorted(B, key=lambda x: (x[0], x[1]))

ans = 0

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

print(ans)

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math





 
def main():
    N = int(input())
    aka = []
    ao = []
    for i in range(N):
        a,b = map(int, input().split())
        aka.append((a,b,False))
            
    for i in range(N):
        c,d = map(int, input().split())
        ao.append((c,d))
            
    ao.sort()
    ans = 0
    for i, val in enumerate(ao):
        c, d = val
        y_max = -1
        index = -1
        for j , vol in enumerate(aka):
            a, b, partner = vol
            if a < c and b < d and partner == False:
                if y_max == -1 or y_max < b:
                    y_max = b
                    index = j
                    
        if y_max != -1:
            ans += 1
            a, b, partner = aka[index]
            partner = True
            aka[index] = (a, b, partner)
            y_max = -1
            index = -1
            
    print(ans)
    
	
if __name__ == "__main__":
	main()

Solution (Python):
import numpy as np

n = int(input())
r = []
b = []

for i in range(n):
    x,y = map(int,input().split())
    r.append([x,y])

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



r.sort(key=lambda x:[x[0],x[1]])
b.sort(key=lambda x:[x[1],x[0]])


ans = 0
for i in range(n):
    x,y = b[i][0],b[i][1]
    tar = 0
    flag = False
    
    
    for j in range(len(r)):
        if r[j][0] < x and r[j][1] < y:
            flag = True
            tar = j
    if flag:
        ans += 1
        r.pop(tar)

print(ans)

Solution (Python):



from operator import itemgetter
n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
red = sorted(red,key = itemgetter(1),reverse = True)
blue = sorted(blue,key = itemgetter(0))
checkr = [True]*n
checkb = [True]*n

pair = 0
for c,d in blue:
    for j in range(n):
        a,b = red[j]
        if a < c and b < d and checkr[j]:
            pair += 1
            checkr[j] = False
            break
print(pair)

Solution (Python):
n = int(input())
info = [list(map(int, input().split())) for i in range(2*n)]

for i in range(n):
    info[i].append("r")
for i in range(n, 2*n):
    info[i].append("b")
info = sorted(info)
a = []
for i in range(2*n):
    a.append(info[i][1:3])
used = [False] * (2*n)
ans = 0
for i in range(2*n):
    for j in range(2*n):
        if a[j][1] == "r" and a[j][0] == 2*n - (i+1):
            tmp = j
            break
    else:
        continue
    for j in range(tmp+1, 2*n):
        if a[j][1] == "b" and a[tmp][0] < a[j][0] and not used[j]:
            used[j] = True
            ans += 1
            break
print(ans)

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                f = self._dfs(from_v, to_v, dist, iter)
                if f == 0:
                    break
                ret += f
        return ret


N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph[i].append((j + N, 1))
for i in range(N):
    graph[S].append((i, 1))
for i in range(N):
    graph[i + N].append((T, 1))

print(Dinic(graph=graph).maximum_flow(S, T))

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                f = self._dfs(from_v, to_v, dist, iter)
                if f == 0:
                    break
                ret += f
        return ret


N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph[i].append((j + N, 1))
for i in range(N):
    graph[S].append((i, 1))
for i in range(N):
    graph[i + N].append((T, 1))

print(Dinic(graph=graph).maximum_flow(S, T))

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        
        vd = [(s, 0)]
        while vd:
            next_vd = []
            for v, d in vd:
                for u, cap, _ in self.graph[v]:
                    if ret[u] < 0 < cap:
                        ret[u] = d + 1
                        next_vd.append((u, d + 1))
            vd = next_vd
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v: 
        :param int to_v: 
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                f = self._dfs(from_v, to_v, dist, iter)
                if f == 0:
                    break
                ret += f
        return ret


N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph[i].append((j + N, 1))
for i in range(N):
    graph[S].append((i, 1))
for i in range(N):
    graph[i + N].append((T, 1))

print(Dinic(graph=graph).maximum_flow(S, T))

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        
        vd = [(s, 0)]
        while vd:
            next_vd = []
            for v, d in vd:
                for u, cap, _ in self.graph[v]:
                    if ret[u] < 0 < cap:
                        ret[u] = d + 1
                        next_vd.append((u, d + 1))
            vd = next_vd
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v: 
        :param int to_v: 
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                f = self._dfs(from_v, to_v, dist, iter)
                if f == 0:
                    break
                ret += f
        return ret


N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            graph[i].append((j + N, 1))
for i in range(N):
    graph[S].append((i, 1))
for i in range(N):
    graph[i + N].append((T, 1))

print(Dinic(graph=graph).maximum_flow(S, T))

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            rev = [i, 0]
            edge = [j + N, 1, rev]
            rev.append(edge)
            graph[i].append(edge)
            graph[j + N].append(rev)
for i in range(N):
    rev = [S, 0]
    edge = [i, 1, rev]
    rev.append(edge)
    graph[S].append(edge)
    graph[i].append(rev)
for i in range(N):
    rev = [i + N, 0]
    edge = [T, 1, rev]
    rev.append(edge)
    graph[i + N].append(edge)
    graph[T].append(rev)


def bfs(s):
    
    ret = [-1] * len(graph)
    ret[s] = 0
    que = deque([(s, 0)])
    while que:
        v, d = que.popleft()
        for u, cap, _ in graph[v]:
            if ret[u] < 0 and cap > 0:
                ret[u] = d + 1
                que.append((u, d + 1))
    return ret


def dinic(v, t, f, dist, iter):
    if v == t:
        return f
    while iter[v] < len(graph[v]):
        edge = graph[v][iter[v]]
        to, cap, rev = edge
        if dist[v] < dist[to] and cap > 0:
            d = dinic(to, t, min(f, cap), dist, iter)
            if d > 0:
                edge[1] -= d
                rev[1] += d
                return d
        iter[v] += 1
    return 0


flow = 0
while True:
    dist = bfs(S)
    if dist[T] < 0:
        break
    while True:
        f = dinic(S, T, INF, dist, [0] * len(graph))
        if f == 0:
            break
        flow += f
print(flow)

Solution (Python):
import sys


N = int(input())

ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort(key=lambda x: -x[1])

cd = [list(map(int, input().split())) for _ in range(N)]
cd.sort(key=lambda x: x[0])

tab = [[] for i in range(N)]
for i, (ci, di) in enumerate(cd):
    for j, (aj, bj) in enumerate(ab):
        if aj < ci and bj < di:
            tab[i].append(j)

ans = 0
used_a = [False] * N
for i in range(N):
    for j in tab[i]:
        if used_a[j]:
            continue
        else:
            ans += 1
            used_a[j] = True
            
            break

print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
CD = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N * 2
T = N * 2 + 1

graph = [[] for _ in range(N * 2 + 2)]
for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            rev = [i, 0]
            edge = [j + N, 1, rev]
            rev.append(edge)
            graph[i].append(edge)
            graph[j + N].append(rev)
for i in range(N):
    rev = [S, 0]
    edge = [i, 1, rev]
    rev.append(edge)
    graph[S].append(edge)
    graph[i].append(rev)
for i in range(N):
    rev = [i + N, 0]
    edge = [T, 1, rev]
    rev.append(edge)
    graph[i + N].append(edge)
    graph[T].append(rev)


def ford_fulkerson(v, t, f, used):
    if v == t:
        return f
    used[v] = True
    for edge in graph[v]:
        to, cap, rev = edge
        if not used[to] and cap > 0:
            d = ford_fulkerson(to, t, min(f, cap), used)
            if d > 0:
                edge[1] -= d
                rev[1] += d
                return d
    return 0


flow = 0
while True:
    f = ford_fulkerson(S, T, INF, [False] * (N * 2 + 2))
    if f == 0:
        break
    flow += f
print(flow)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
R = []
B = []
ans = 0
for i in range(N):
  a,b = map(int,input().split())
  R.append((a,b))
for i in range(N):
  c,d = map(int,input().split())
  B.append((c,d))
R.sort(key=lambda x:x[0])
B.sort(key=lambda x:x[0])
H = []
l = 0
for i in range(N):
  for j in range(l,N):
    if R[j][0] > B[i][0]:
      l = j
      break
    H.append(R[j])
  H.sort(key=lambda x:x[1], reverse=True)
  for k in range(len(H)):
    if H[k][1] < B[i][1]:
      H.pop(k)
      ans += 1
      break
print(ans)

Solution (Python):
n=int(input())
r=[list(map(int,input().split()))for _ in range(n)]
b=sorted([list(map(int,input().split()))for _ in range(n)])
p=0
for i in range(n):
  c=[]
  for j in range(len(r)):
    if r[j][0]<b[i][0] and r[j][1]<b[i][1]:c.append(r[j][::-1])
  if len(c)==0:continue
  c.sort(reverse=1)
  del r[r.index(c[0][::-1])]
  p+=1
print(p)