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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
        # PyPy で deque 遅いのでリストで
        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))

Submission status: Accepted

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

Submission status: Accepted

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

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
            # print("#", ab[j], cd[i])
            break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Bipartite_Matching():
    # n : 頂点数
    def __init__(self, n):
        self.match = [-1]*n
        self.used = [0]*n
        self.n = n
        self.edges = [[] for i in range(n)]

    # u→v のedgeを張る
    def add_edge(self, u, v):
        self.edges[u].append(v)

    # 増加路の判定
    def dfs(self, v):
        self.used[v] = 1
        for u in self.edges[v]:
            w = self.match[u]
            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[v] = u
                self.match[u] = v
                return True
        return False

    # 最大マッチングの辺数を返す
    def bipartite_matching(self):
        ret = 0
        for v in range(self.n):
            if self.match[v] < 0:
                self.used = [0]*self.n
                if self.dfs(v):
                    ret += 1
        return ret


n = int(input())
BP = Bipartite_Matching(2*n)
red = [None]*n
for i in range(n):
    a, b = map(int, input().split())
    red[i] = (a, b)
blue = [None]*n
for i in range(n):
    c, d = map(int, input().split())
    blue[i] = (c, d)

# blue をすべて見て、redを探す
for i in range(n):
    c, d = blue[i]
    for j in range(n):
        a, b = red[j]
        if a < c and b < d:
            BP.add_edge(n+i, j)
            BP.add_edge(j, n+i)
ans = BP.bipartite_matching()
print(ans)

Submission status: Accepted

Solution code:
def bipertite_matching(N, edges):
    def dfs(v):
        used[v] = True
        for u in edges[v]:
            w = match[u]
            if w < 0 or (used[w] == False and dfs(w)):
                match[v] = u
                match[u] = v
                return True
        return False
    match = [-1 for _ in range(N)]
    ret = 0
    for v in range(N):
        if match[v] < 0:
            used = [False for _ in range(N)]
            if dfs(v):
                ret += 1
    return ret

N = int(input())
a, b = [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())
c, d = [None] * N, [None] * N
for i in range(N):
    c[i], d[i] = map(int, input().split())
es = [[] for i in range(2 * N)]
for i in range(N):
    for j in range(N):
        if a[i] < c[j] and b[i] < d[j]:
            es[i].append(N+j)
            es[N+j].append(i)
print(bipertite_matching(2*N, es))

Submission status: Accepted

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

reds.sort()
blues.sort()
 
ans = 0
for blue in blues:
    c, d = blue
 
    # 条件に当てはまる赤を抽出
    targets = [red for red in reds if red[0] < c and red[1] < d]
    targets.sort(key=lambda x:x[1])
 
    # 赤のうち一番y座標が大きいものを抽出
    if targets:
        target = targets.pop()
        reds.remove(target)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

reds.sort()
blues.sort()

ans = 0
for blue in blues:
    c, d = blue

    # 条件に当てはまる赤を抽出
    targets = [red for red in reds if red[0] < c and red[1] < d]
    targets.sort(key=lambda x:x[1])

    # 赤のうち一番y座標が大きいものを抽出
    if targets:
        target = targets.pop()
        reds.remove(target)
        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()
#print(f'B:{B}')
R.sort(key=lambda x: -x[1])
#print(f'R:{R}')
cnt = 0
for b in B:
    #print('----------------------------------------------------')
    bx = b[0]; by = b[1]
    #print(f'bx:{bx} by:{by}')
    for ir, r in enumerate(R):
        rx = r[0]; ry = r[1]
        #print(f'rx:{rx} ry:{ry}')
        if rx < bx and ry < by:
            R.pop(ir)
            cnt += 1
            break
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) ]
R.sort(key=lambda x:x[1],reverse=1)
B.sort()
ans=0
for b in B:
    for r in R:
        if b[1]>r[1] and b[0]>r[0]:
            ans+=1
            R.remove(r)
            break
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    ab_list = [list(map(int, input().split())) for i in range(N)]
    cd_list = [list(map(int, input().split())) for i in range(N)]

    ab_list = sorted(ab_list, key=lambda x : x[1], reverse=True)
    cd_list = sorted(cd_list, key=lambda x : x[0])

    answer = 0
    for b in cd_list:
        for r in ab_list:
            if b[0]>r[0] and b[1]>r[1]:
                answer += 1
                ab_list.remove(r)
                break
    print(answer)

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
cd=[list(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda x:x[1], reverse=True)
cd.sort()
ans=0
for i in range(n):
    for a in ab:
        if a[0]<cd[i][0] and a[1]<cd[i][1]:
            ab.remove(a)
            ans+=1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N)]
cd = [LIST() for _ in range(N)]

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

ans = 0
for c, d in cd:  # 青の点
	for i in range(len(ab)):  # 赤の点
		if c > ab[i][0] and d > ab[i][1]:  # マッチング
			# print(ab[i], c, d)
			ab.pop(i)
			ans += 1
			break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

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


a2=sorted(a, key=lambda x: x[1])
b2=sorted(b, key=lambda x: x[0])

ans=0
for i in range(n):
    for j in range(n):
        if b2[i][0]>a2[n-1-j][0] and b2[i][1]>a2[n-1-j][1]:
            ans+=1
            a2[n-1-j][0]=3*n
            break

print(ans)

Submission status: Accepted

Solution code:
# 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

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

D = Dinic(N*2+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]:
            D.add_edge(i,j+N,1)

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

print(D.flow(N*2,N*2+1))

Submission status: Accepted

Solution code:
n=int(input())
point=[]
for i in range(n):
    a,b=map(int,input().split())
    point.append((b,a,0))
for i in range(n):
    a,b=map(int,input().split())
    point.append((b,a,1))
point.sort()
stock=[]
ans=0
for p in point:
    if p[2]==0:
        stock.append(p)
    else:
        if stock==[]:
            pass
        else:
            I=-1
            D=300
            for i in range(len(stock)):
                if stock[i][1]<p[1]:
                    if p[1]-stock[i][1]<D:
                        D=p[1]-stock[i][1]
                        I=i
            if I==-1:
                pass
            else:
                ans=ans+1
                del stock[I]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ab=sorted([list(map(int,input().split())) for _ in [0]*N],key=lambda x:x[1],reverse=True)
cd=sorted([list(map(int,input().split())) for _ in [0]*N],key=lambda x:x[0])
cnt=0
for i in range(N):
    for a in ab:
        if a[0]<cd[i][0] and a[1]<cd[i][1]:
            ab.remove(a)
            cnt+=1
            break
print(cnt)

Submission status: Accepted

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

ab=[x[0]+x[1]*1j for x in ab]
cd=[x[0]+x[1]*1j for x in cd]

def comp(a,b):
	if a.real<b.real and a.imag<b.imag:
		return True
	else:
		return False

abd=dict()
cdd=dict()

for i in range(len(ab)):
	temp=[]
	for j in range(len(cd)):
		if comp(ab[i],cd[j]):
			temp.append(cd[j])
	if temp!=[]:
		abd[ab[i]]=temp
	
for i in range(len(cd)):
	temp=[]
	for j in range(len(ab)):
		if comp(ab[j],cd[i]):
			temp.append(ab[j])
	if temp!=[]:
		cdd[cd[i]]=temp
	
ans=0
while(len(abd.keys())+len(cdd.keys())):
	m=10**5
	
	for i in abd.keys():
		for j in abd[i]:
			cnt=len(abd[i])+len(cdd[j])
			if cnt<m:
				m=cnt
				abm=i
				cdm=j
	
	cdl=abd[abm]
	abl=cdd[cdm]
	
	for i in abl:
		abd[i].remove(cdm)
	for i in cdl:
		cdd[i].remove(abm)
	
	del abd[abm]
	del cdd[cdm]
	
	abk=[i for i in abd.keys()]
	cdk=[i for i in cdd.keys()]
	
	for i in abk:
		if abd[i]==[]:
			del abd[i]
	for i in cdk:
		if cdd[i]==[]:
			del cdd[i]
	ans+=1
print(ans)

Submission status: Accepted

Solution code:
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])
blue.sort()
red.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b in blue:
    for i, r in enumerate(red):
        if (r[0] < b[0]) & (r[1] < b[1]):
            ans += 1
            red.pop(i)
            break
print(ans)

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


import queue
from collections import defaultdict
def max_flow(edges, num_of_vertices, start, goal):
    level = defaultdict(lambda: -1)
    seen = set()

    def bfs(s):
        level[s] = 0
        q = queue.Queue()
        q.put(s)
        while not q.empty():
            v = q.get()
            for nv, cap in edges[v].items():
                if cap > 0 and level[nv] < 0:
                    level[nv] = level[v] + 1
                    q.put(nv)

    def dfs(v, t, f):
        if v == t:
            return f
        for nv, cap in edges[v].items():
            if (v, nv) in seen:
                continue
            seen.add((v, nv))
            if cap > 0 and level[v] < level[nv]:
                d = dfs(nv, t, min(f, cap))
                if d > 0:
                    edges[v][nv] -= d
                    edges[nv][v] += d
                    return d
        return 0

    flow = 0
    while True:
        level.clear()
        bfs(start)
        if level[goal] < 0:
            return flow
        seen.clear()
        while True:
            f = dfs(start, goal, float('inf'))
            if f == 0:
                break
            flow += f
    return flow

N = n()

reds = []
edges = defaultdict(dict)

for i in range(N):
    reds.append(nl())
    edges[0][i+1] = 1
    edges[i+1][0] = 0
blues = []
for i in range(N):
    blues.append(nl())
    edges[N+i+1][2*N+1] = 1
    edges[2*N+1][N+i+1] = 0

for i in range(N):
    for j in range(N):
        rx, ry = reds[i]
        bx, by = blues[j]
        if rx < bx and ry < by:
            edges[i+1][N+j+1] = 1
            edges[N+j+1][i+1] = 0

print(max_flow(edges, 2*N+2, 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[1], reverse=True)
blue = sorted(blue, key=lambda x: x[0], reverse=False)

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split()))+[0] for i in range(N)] + [[2*N+1, -1, 0]]
B = [list(map(int, input().split())) for i in range(N)]
B.sort()


cnt = 0
for a,b in B:
    idx = -1
    for j in range(N):
        c,d,used = A[j]
        if a > c and b > d and used == 0 and A[idx][1] < d:
            idx = j
    if idx != -1:
        A[idx][2] = 1
        cnt += 1
        # print(a,b,A[idx])
print(cnt)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
# 二部グラフ完全マッチング
# 最大フロー
N = int(input())
NN = N * 2
XY = [[int(x) for x in input().split()] for _ in range(NN)]
graph = [[0] * (NN+2) for _ in range(NN+2)]
start = NN
goal = NN+1

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

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

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

answer = max_flow(graph)
print(answer)

Submission status: Accepted

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

ans = 0
for b in blue:
    tmp_y = -1
    pop_i = None
    flag = False
    for i, r in enumerate(red):
        if r[0] >= b[0]:
            break
        if r[1] < b[1]:
            flag = True
            if r[1] >= tmp_y:
                pop_i = i
                tmp_y = r[1]
    if flag:
        red.pop(pop_i)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
R=[]
B=[]
for i in range(n):
    r=[int(i) for i in input().split()]
    R.append(r)
R.sort(key=lambda x:x[0])
for i in range(n):
    b=[int(i) for i in input().split()]
    B.append(b)
B.sort(key=lambda x:x[0])
ans=0
for b in B:
    stock=[]
    for r in R:
        if r[0]<b[0] and r[1]<b[1]:
            stock.append(r)
    if 0<len(stock):
        stock.sort(key=lambda x:x[1],reverse=True)
        red=stock[0]
        ans+=1
        R.remove(red)
#        print(b)
#        print(red)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

alist.sort(reverse=True)
blist.sort()

ans = 0
for i in range(N):
    for j in range(len(alist)):
        if blist[i][0] > alist[j][1] and blist[i][1] > alist[j][0]:
            ans += 1
            alist = alist[:j] + alist[j+1:]
            break

print(ans)

Submission status: Accepted

Solution code:
# 写経
n = int(input())
lst_r = [list(map(int, input().split())) for _ in range(n)]
lst_b = [list(map(int, input().split())) for _ in range(n)]
lst_r.sort(key=lambda x:-x[1])
lst_b.sort()


ans = 0
for b in lst_b:
    for r in lst_r:
        if r[0] < b[0] and r[1] < b[1]:
            ans += 1
            lst_r.remove(r)
            break


print(ans)

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