Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All input values are integers.

1 \leq N \leq 100

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum number of friendly pairs.

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

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

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



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


Sample output:
2

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque

class Dinic:
    def __init__(self,n,edges):
        self.n=n
        self.edges=[[] for _ in range(n)]
        self.iter=[0]*n
        self.level=None
        self.graph(edges)
    def graph(self,E):
        edges=self.edges
        for fr,to,cap in E:
            edges[fr].append([to,cap,len(edges[to])])
            edges[to].append([fr,0,len(edges[fr])-1])
    def maxflow(self,source,sink):
        max_flow=0
        while True:
            self.bfs(source)
            if self.level[sink]<0:
                return max_flow
            self.iter=[0]*self.n
            flow=self.dfs(source,sink,float('inf'))
            while flow:
                max_flow+=flow
                flow=self.dfs(source,sink,float('inf'))
    def bfs(self,source):
        edges=self.edges
        level=[-1]*self.n
        level[source]=0
        q=deque([source])
        while q:
            fr=q.popleft()
            for to,cap,_ in edges[fr]:
                if cap>0>level[to]:
                    level[to]=level[fr]+1
                    q.append(to)
        self.level=level
    def dfs(self,source,sink,flow):
        if source==sink:
            return flow
        while self.iter[source]<len(self.edges[source]):
            to,cap,rev=self.edges[source][self.iter[source]]
            if cap>0 and self.level[source]<self.level[to]:
                f=self.dfs(to,sink,min(flow,cap))
                if f:
                    self.edges[source][self.iter[source]][1]-=f
                    self.edges[to][rev][1]+=f
                    return f
            self.iter[source]+=1
        return 0

def BipartiteMatching(Pairs,a,b):
    Edges=[]
    for x,y in Pairs:
        Edges.append((x+1,a+y+1,1))
    for x in range(a):
        Edges.append((0,x+1,1))
    for y in range(b):
        Edges.append((a+y+1,a+b+1,1))
    solver=Dinic(a+b+2,Edges)
    return solver.maxflow(0,a+b+1)

n=int(input())
R=[list(map(int,input().split())) for _ in range(n)]
B=[list(map(int,input().split())) for _ in range(n)]
Pairs=[]
for i in range(n):
    for j in range(n):
        if R[i][0]<B[j][0] and R[i][1]<B[j][1]:
            Pairs.append((i,j))
print(BipartiteMatching(Pairs,n,n))

Submission status: Accepted

Solution code:
class Queue:
    def __init__(self):
        self.__count = 0
        self.__data = []

    def count(self) -> int:
        return self.__count

    def empty(self) -> bool:
        return self.__count == 0

    def front(self):
        if self.empty():
            raise Exception('empty')
        return self.__data[0]

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        res, self.__data = self.__data[0], self.__data[1:]
        self.__count -= 1
        return res

    def enqueue(self, v):
        self.__data.append(v)
        self.__count += 1


class Edge:
    def __init__(self, v: int, cap: int, rev: int):
        """
        :param v: to
        :param cap: capacity
        :param rev: revesed to
        """
        self.v = v
        self.cap = cap
        self.rev = rev

        self.flow = 0


class Graph:
    def __init__(self, num_v: int):
        """
        :param num_v: number of vertex
        """
        self.num_v = num_v
        self.level = [0] * num_v
        self.graph = [[] for _ in range(num_v)]

    def add_edge(self, u: int, v: int, cap: int):
        """add edge
        :param u: from
        :param v: to
        :param cap: capacity
        """
        forward = Edge(v, cap, len(self.graph[v]))
        back = Edge(u, 0, len(self.graph[u]))

        self.graph[u].append(forward)
        self.graph[v].append(back)

    def __bfs(self, s: int, t: int) -> bool:
        """Finds if more flow can be sent from s to t.
        Also assigns level to nodes.
        :param s: source
        :param t: sink
        :return: `True` if finds more flow can be sent from s to t.
        """
        self.level = [-1] * self.num_v
        self.level[s] = 0

        q = Queue()
        q.enqueue(s)
        while not q.empty():
            u = q.dequeue()

            for e in self.graph[u]:
                # not yet visited, and flow can be sent more
                if self.level[e.v] < 0 and e.flow < e.cap:
                    # level of v is level of its parent + 1
                    self.level[e.v] = self.level[u] + 1

                    q.enqueue(e.v)

        return self.level[t] >= 0

    def __send_flow(self,
                    u: int, flow: int, t: int, start: list = None) -> int:
        """send `flow` from `u` to `t`.
        :param u: from
        :param flow: flow
        :param t: to
        :param start: explored vertex
        :return: value of flow can be sent from u to t.
        """
        if u == t:
            return flow

        if start is None:
            start = [0] * (self.num_v + 1)

        while start[u] < len(self.graph[u]):
            e = self.graph[u][start[u]]

            if self.level[e.v] != self.level[u] + 1:
                # skip if level of e.v is not next to
                # u's one.
                start[u] += 1
                continue
            if not (e.flow < e.cap):
                # skip if flow cannot be sent more to
                # v.
                start[u] += 1
                continue

            cur_f = min(flow, e.cap - e.flow)
            tmp_f = self.__send_flow(e.v, cur_f, t, start)

            if tmp_f > 0:
                # add flow to current edge
                e.flow += tmp_f
                # subtract flow from reverse edge of current one.
                self.graph[e.v][e.rev].flow -= tmp_f

                return tmp_f

            start[u] += 1

        return 0

    def maximum_flow(self, s: int, t: int) -> int:
        """maximum flow from s to t.
        :param s: from
        :param t: to
        :return: maximum flow
        """
        if s == t:
            return 0

        max_flow = 0
        while self.__bfs(s, t):
            while True:
                flow = self.__send_flow(s, float('inf'), t)
                if flow == 0:
                    break
                max_flow += flow
        return max_flow


def _2d_plane_2n_points(N: int, reds: list, blues: list) -> int:
    reds = sorted(reds, key=lambda x: x[0])
    blues = sorted(blues, key=lambda x: x[0])

    # bipartite matching
    g = Graph(2*N + 2)
    s, t = 0, 2*N+1

    def blue_idx(i): return i + 1
    def red_idx(i): return N + i + 1

    # add edges from source to blue stars and
    # from red stars to sink
    for i in range(N):
        b, r = blue_idx(i), red_idx(i)
        g.add_edge(s, b, 1)
        g.add_edge(r, t, 1)

    # add edges from blue star to red star
    # when rx < ry and bx < by
    for i, (bx, by) in enumerate(blues):
        bi = blue_idx(i)

        for j, (rx, ry) in enumerate(reds):
            if not (rx < bx):
                break
            if not (ry < by):
                continue

            ri = red_idx(j)
            g.add_edge(bi, ri, 1)

    return g.maximum_flow(s, t)


if __name__ == "__main__":
    N = int(input())
    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]
    ans = _2d_plane_2n_points(N, reds, blues)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Red = [ list(map(int,input().split() ) ) for i in range(N) ]
Blue = [ list(map(int,input().split() ) ) for i in range(N) ]
Red.sort(reverse=True,key=lambda x:x[1])
Blue.sort()
count = 0
for B in Blue:
    for i in range(len(Red)):
        #print("i:",i)
        #print("Red[i][0]:",Red[i][0])
        #print("Red[i][1]:",Red[i][1])
        if (B[0] > Red[i][0]) and (B[1] > Red[i][1]) :
            #print("B:", B)
            #print("Red[i]:",Red[i] )
            count += 1
            Red[i][0] = 1000
            B[0] = -1
            continue
        
print(count)

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([list(map(int,input().split())) for _ in range(N)], key = lambda x: -x[1])
CD = sorted([list(map(int,input().split())) for _ in range(N)])

cnt = 0
for c, d in CD:
  for a, b in AB:
    if(a < c and b < d):
      cnt += 1
      AB.remove([a, b])
      break
print(cnt)

Submission status: Accepted

Solution code:
def ans():
  N = int(input())
  AB = sorted([list(map(int,input().split())) for _ in range(N)], key = lambda x: -x[1])
  CD = sorted([list(map(int,input().split())) for _ in range(N)])
  cnt = 0
  for c, d in CD:
    for a, b in AB:
      if(a < c and b < d):
        cnt += 1
        AB.remove([a,b])
        break
  print(cnt)
ans()

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int, input().split())) for i in range (N)]
blue = [list(map(int, input().split())) for i in range (N)]
blue.sort(key=lambda x:x[0])
red.sort(key=lambda x:x[1], reverse=True)
pairs = 0
flag = [True for i in range(N)]
for i in range(N):
    for j in range(N):
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1] and flag[j]:
            pairs += 1
            flag[j] = False
            break
print(pairs)

Submission status: Accepted

Solution code:
# 深さ優先探索してパスを返す
def DFS(L, s, t):
  S = [[s, 0]]
  P = [0] * T
  D = [0] * len(L)
  while S != []:
    k = S.pop()
    P[k[1]] = k[0]
    if L[k[0]][T - 1] > 0:
      P[k[1] + 1] = T - 1
      return P
    for i in range(len(L)):
      if D[i] == 0 and L[k[0]][i] > 0:
        S.append([i, k[1] + 1])
        D[i] = 1
  return False  

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

T = 2 * N + 2
L = [[0] * T for i in range(T)]

# 0 -> s
# 1 ~ N -> red
# N + 1 ~ 2N -> blue
# 2N + 1 -> t

ab.sort()
cd.sort()
cnt = 0

# 書記設定
for i in range(0, N):
  L[0][i + 1] = 1
  L[N + 1 + i][T - 1] = 1
  for j in range(cnt, N):
    if ab[i][0] > cd[j][0]:
      cnt += 1
      continue
    if ab[i][1] < cd[j][1]:
      L[i + 1][N + 1 + j] = 1

while True:
  # s -> t のパスを一つ取得
  # パスがなければ終了
  P = DFS(L, 0, T - 1)
  if P == False:
    break
  # 流せる最大値を取得
  mi = 10 ** 20
  Last = T
  for i in range(1, Last):
    t = L[P[i - 1]][P[i]]
    if t < mi:
      mi = t
    if P[i] == T - 1:
      Last = i + 1
      break
  # リストを更新
  for i in range(1, Last):
    L[P[i - 1]][P[i]] -= 1
    L[P[i]][P[i - 1]] += 1

print(sum(L[-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)]

ab.sort(reverse = True)
cd.sort(reverse = True)

cd += [[1000, 1000]]

L = [0] * N
Ans = 0
for i in range(N):
  t = ab[i]
  mi = N
  for j in range(N):
    k = cd[j]
    if t[0] > k[0]:
      break
    if L[j] == 1: continue
    if t[1] > k[1]: continue
    if cd[mi][1] > k[1]:
      mi = j
  if mi != N:
    L[mi] = 1
    Ans += 1
      
print(Ans)

Submission status: Accepted

Solution code:

N = int(input())
red_ls = list()
blue_ls = list()
for i in range(N):
    red_ls.append([int(i) for i in input().split()])
for i in range(N):
    blue_ls.append([int(i) for i in input().split()])


red_ls = sorted(red_ls, key=lambda x:(x[1], x[0]), reverse=True)
#red_x, red_y = zip(*red_ls)
blue_ls = sorted(blue_ls, key=lambda x:(x[0], x[1]))

cnt = 0
pre_ind = -1
yet_ls = list()
for (blue_x, blue_y) in blue_ls:
    flg = 0
    for ind, (red_x, red_y) in enumerate(red_ls):
        if red_y >= blue_y:
            continue
        if red_x >= blue_x:
            continue
        if ind in yet_ls:
            continue
        cnt += 1
        yet_ls.append(ind)
        break
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]
b=[list(map(int,input().split()))for i in range(n)]
b.sort()
a=sorted(a,key=lambda x:-x[1])
d=0
for i in range(n):
    for j in range(len(a)):
        if b[i][0]>a[j][0] and b[i][1]>a[j][1]:
            d+=1
            del a[j]
            break
print(d)

Submission status: Accepted

Solution code:
import heapq


def main():
    N = int(input())
    R = [list(map(int, input().split())) + ['R'] for _ in range(N)]
    B = [list(map(int, input().split())) + ['B'] for _ in range(N)]
    P = R + B
    P.sort(key=lambda x: (x[0], x[1]))
    solo = []
    ans = 0
    for p in P:
        x, y, c = p
        if c == 'R':
            solo.append((x, y))
        else:
            tmp = (-1, -1)
            for s in solo:
                if s[0] < x and tmp[1] < s[1] < y:
                    tmp = s
            if tmp != (-1, -1):
                solo.remove(tmp)
                ans += 1
    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)]
b.sort()
r = sorted(r,key=lambda x:-x[1])
ans = 0
for i,b_ in enumerate(b):
    for j,r_ in enumerate(r):
        if b_[0]>r_[0] and b_[1]>r_[1]:
            ans+=1
            del r[j]
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    R = []
    for _ in range(N):
        a, b = map(int, input().split())
        R.append([a, b])
    B = []
    for _ in range(N):
        c, d =  map(int, input().split())
        B.append([c, d])
    R = sorted(R, key=lambda x: x[0])
    B = sorted(B, key=lambda x: x[0])

    ans = 0
    used = []
    for i in range(N):
        x, y = -1, -1
        j = 0
        while j < N and R[j][0] < B[i][0]:
            s, t = R[j][0], R[j][1]
            if t < B[i][1] and t > y and s not in set(used):
                x = s
                y = t
            j += 1
                
        if x >= 0:
            used.append(x)
    print(len(used))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

"""
参考：https://www.hamayanhamayan.com/entry/2018/03/18/085108
　　　http://vartkw.hatenablog.com/entry/2016/12/02/002703
　　　https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow
・二部最大マッチング
・最大流アルゴリズム(Dinic法)
・まだ理解不十分な点はあると思うけど、初めて見た時よりは見慣れた。
"""

from collections import deque

class BipartiteMatching:

	def __init__(self, n, m):
		self.n = n
		self.m = m
		# ペアとして有りうる相手を格納する
		self.E = [[] * (n+m+2) for i in range(n+m+2)]
		# 決まったペアを格納する
		self.match = [0] * (n+m+2)
		# 距離(付け替え候補を決める時の深さみたいなものが入ってる)
		self.dist = [0] * (n+m+2)
	
	def bfs(self):
		que = deque()
		for i in range(1, self.n+1):
			# マッチングの決まっていないノードをキューに詰める
			if not self.match[i]:
				self.dist[i] = 0
				que.append(i)
			else:
				self.dist[i] = float('inf')
		self.dist[0] = float('inf')
		while len(que) != 0:
			u = que.popleft()
			if u != 0:
				for v in self.E[u]:
					if self.dist[self.match[v]] == float('inf'):
						self.dist[self.match[v]] = self.dist[u] + 1
						# 付け替えの候補になりうるノードがここで追加されていく
						que.append(self.match[v])
		# フローを流せるエッジが存在しなければ、dist[0]がINFのまま(Falseを返して終了)
		return self.dist[0] != float('inf')

	def dfs(self, u):
		if u != 0:
			for v in self.E[u]:
				if self.dist[self.match[v]] == self.dist[u] + 1:
					if self.dfs(self.match[v]):
						# ペア確定(あとで変わることもある)
						self.match[v] = u
						self.match[u] = v
						return True
			# 今回決められなかったノード
			self.dist[u] = float('inf')
			return False
		return True
	
	def add(self, a, b):
		b += self.n
		self.E[a+1].append(b+1)
		self.E[b+1].append(a+1)

	def whois(self, x):
		return self.match[x+1]-1

	def solve(self):
		for i in range(self.n+self.m+1):
			self.match[i] = 0
		res = 0
		while self.bfs():
			for i in range(1, self.n+1):
				# 前から順に繋げる所は繋いでいって、
				# もっといいのがあれば後から付け替える
				if not self.match[i] and self.dfs(i):
					res += 1
		return res

N = int(input())
aN, bN, cN, dN = [0] * N, [0] * N, [0] * N, [0] * N
# 赤い点
for i in range(N):
	aN[i], bN[i] = map(int, input().split())
# 青い点
for i in range(N):
	cN[i], dN[i] = map(int, input().split())

# (赤い点の数, 青い点の数)
bm = BipartiteMatching(N, N)
for i in range(N):
	for j in range(N):
		if aN[i] < cN[j] and bN[i] < dN[j]:
			# ペア候補として適切な組を追加していく(0-indexed)
			bm.add(i, j)
print(bm.solve())

Submission status: Accepted

Solution code:
import math

N = int(input())
ab = []
cd = []

for i in range(N):
    ab.append(list(map(int,input().split())))

for i in range(N):
    cd.append(list(map(int,input().split())))

res = 0

cd.sort()

for i in range(len(cd)):
    c,d = cd[i]
    max_b = -1
    index = -1
    tmp_list = 0
    for j in range(len(ab)):
        a,b = ab[j]
        if a > c or b > d:
            continue
        
        tmp_b = b

        if max_b < b:
            max_b = tmp_b
            index = j

    if index > -1:
        ab.pop(index)
        res += 1

print(res)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    red = sorted(
        [list(map(int, input().split())) for _ in range(N)],
        key=lambda x: x[1],
        reverse=True
    )
    blue = sorted(
        [list(map(int, input().split())) for _ in range(N)],
        key=lambda x: x[0]
    )
    ans = 0
    for b in blue:
        for i, r in enumerate(red):
            if b[0] > r[0] and b[1] > r[1]:
                ans += 1
                red.pop(i)
                break
    print(ans)


main()

Submission status: Accepted

Solution code:
n = int(input())
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]
red.sort()
blue.sort()
#greedy
ret = 0
used = set()
for x, y in blue:
    koho = -1
    mostright = -1
    for i in range(len(red)):
        if i not in used:
            if red[i][0] >= x:
                break
            elif y > red[i][1] > mostright:
                koho = i
                mostright = red[i][1]
    if koho != -1:
        ret += 1
        used.add(koho)
print(ret)

Submission status: Accepted

Solution code:
#ABC091C
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(tuple(map(int,input().split())))
for j in range(n):
    blue.append(tuple(map(int,input().split())))
blue.sort(key=lambda x:x[0])
red.sort(key=lambda x:x[0])
ans=0
for i in range(n):
    ymax=-1
    maxidx=-1
    for j in range(len(red)):
        if red[j][0]>=blue[i][0]:break
        if ymax< red[j][1] <blue[i][1]:
            ymax=red[j][1]
            maxidx=j
    if maxidx==-1:continue
    else:
        red.pop(maxidx)
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
B = [list(map(int,input().split())) for i in range(n)]
A.sort(reverse=1, key=lambda x:x[1])
B.sort()            
#print(A)
#print(B)

ans=0

for i in range(n):
    ma=-1
    mai=-1
    for j in range(len(A)):
        #print("{} {}".format(i,j))
        #print(A)
        if B[i][0]>A[j][0] and B[i][1]>A[j][1] :
            if ma<A[j][1] :
                mai=j
                ma=A[j][1]
                #print("A")
    if mai!=-1 :
        del A[mai]
        ans+=1
            

print(ans)

Submission status: Accepted

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

A.sort(key=lambda x: x[0], reverse=True)
B.sort(key=lambda x: x[1])


flag1 = [False for _ in range(N)]
flag2 = [False for _ in range(N)]

res = 0
for i in range(N):
    for j in range(N):
        if A[i][0] < B[j][0] and A[i][1] < B[j][1] and flag1[i] == False and flag2[j] == False:
            res += 1
            flag1[i] = True
            flag2[j] = True

print(res)

Submission status: Accepted

Solution code:
from operator import itemgetter
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)]
blue.sort()
red2=sorted(red,key=itemgetter(1))
red3=[]
for x in red2[::-1]:
  red3.append(x)
count=0
for i in range(N):
  redlen=len(red3)
  j=0
  for j in range(redlen):
    if red3[j][0]<blue[i][0] and red3[j][1]<blue[i][1]:
      count+=1
      del red3[j]
      break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
r = [list(map(int,input().split())) for _ in range(n)]
b = [list(map(int,input().split())) for _ in range(n)]
r.sort(key=lambda x:x[1])
b.sort()
cnt = 0
for i in range(n):
    R = []
    for j in range(n):
        if 0 <= r[j][0] < b[i][0] and 0 <= r[j][1] < b[i][1]:
            R.append([r[j][1],j])
            
    R.sort(reverse=True)
    if len(R) >= 1:
        cnt += 1
        r[R[0][1]][0] = -1
        r[R[0][1]][1] = -1

print(cnt)

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])
res = 0
for i in range(len(blue)):
    index = -1
    maxy = -1
    for j in range(len(red)):
        if red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
            if red[j][1] > maxy:
                maxy = red[j][1]
                index = j
    if index != -1:
        red.pop(index)
        res += 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([list(map(int,input().split())) for _ in range(N)], key = lambda x: -x[1])
CD = sorted([list(map(int,input().split())) for _ in range(N)])

cnt = 0
for c, d in CD:
  for a, b in AB:
    if(a < c and b < d):
      cnt += 1
      AB.remove([a,b])
      break
print(cnt)

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 i in range(n)]
red=sorted(red,key=lambda x:-x[1])
blue=sorted(blue)
count=0
i=0
while i<len(blue):
    for j in range(len(red)):
        if red[j][0]<blue[i][0] and red[j][1]<blue[i][1]:
            count+=1
            del red[j]
            del blue[i]
            break
    else:
        i+=1
print(count)

Submission status: Accepted

Solution code:
import numpy as np

def input_numbers():
    temp = list(map(int, input().split()))
    return temp

def GCD(a, b):
    if(a < b):
        temp = a
        a = b
        b = temp
    a = a % b
    if(a == 0):
        return b
    else:
        return GCD(a, b)

class point:
    def __init__(self, x ,y):
        self.x = x
        self.y = y

n = int(input())

R_point = []
B_point = []

for i in range(n):
    temp = input_numbers()
    R_point += [point(temp[0], temp[1])]

for i in range(n):
    temp = input_numbers()
    B_point += [point(temp[0], temp[1])]

B_point.sort(key = lambda point:point.x)
R_point.sort(key = lambda point:point.y)
R_point.reverse()

count = 0

for i in range(len(B_point)):
    for j in range(len(R_point)):
        if(R_point[j].x < B_point[i].x and R_point[j].y < B_point[i].y):
            R_point.pop(j)
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
AB = sorted([[int(i) for i in input().split()] for i in range(n)], reverse = True)
CD = sorted([[int(i) for i in input().split()] for i in range(n)], key = lambda x: x[1])

cnt = 0
for a, b in AB:
    for cd in CD:
        if a < cd[0] and b < cd[1]:
            cnt += 1
            CD.remove(cd)
            break
            
print(n - len(CD))

Submission status: Accepted

Solution code:
import collections


class FordFulkerson:
    """
    Verified with http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
    """

    def __init__(self):
        self.g = collections.defaultdict(lambda: collections.defaultdict(int))

    def add_edge(self, u, v, c):
        self.g[u][v] = c

    def dfs(self, u, t, f, used: set):
        """
        :param u: visiting node
        :param t: sink
        :param f: flow
        :param used: node u is used?
        :return: min(c, f)
        """
        if u == t:
            return f

        used.add(u)

        # visit next node
        for v, c in self.g[u].items():
            if v not in used and c > 0:
                f = min(c, f)
                d = self.dfs(v, t, f, used)

                # update the graph if a path is found
                if d > 0:
                    self.g[u][v] -= d
                    self.g[v][u] += d
                    return d

        # path is not found
        return 0

    def max_flow(self, s, t):
        """Calculate maximum flow from s to t on the network

        :param s: source
        :param t: sink
        :return: max flow on the network
        """
        f = 0
        while True:
            d = self.dfs(s, t, float("inf"), set())
            if d == 0:  # nothing to update any more
                break
            f += d
        return f


def bipartite_matching(pairs: list, X :int, Y: int):
    solver = FordFulkerson()
    s = X+Y
    t = s+1
    for x, y in pairs:
        solver.add_edge(x, X+y, 1)
    for x in range(X):
        solver.add_edge(s, x, 1)
    for y in range(Y):
        solver.add_edge(X+y, t, 1)

    return solver.max_flow(s, t)


def main():
    N = int(input())
    rs = []
    bs = []
    for i in range(N):
        x, y = map(int, input().split())
        rs.append((x, y))
    for i in range(N):
        x, y = map(int, input().split())
        bs.append((x, y))

    pairs = []
    for i in range(N):
        for j in range(N):
            r = rs[i]
            b = bs[j]
            if r[0]<b[0] and r[1]<b[1]:
                pairs.append((i, j))
    print(bipartite_matching(pairs, N, N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
R=[[0,0,0] for _ in range(N)]
B=[[0,0,0] for _ in range(N)]
for i in range(N):
    R[i][0],R[i][1]=map(int,input().split())
for i in range(N):
    B[i][0],B[i][1]=map(int,input().split())
R.sort(key=lambda x:x[1],reverse=True)
B.sort()
cnt=0
for b in B:
    for r in R:
        if b[0]>r[0] and b[1]>r[1] and r[2]==0:
            cnt+=1
            r[2]=1
            break
print(cnt)

Submission status: Accepted

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

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

red.sort(key=lambda x:x[1], reverse=True)
blu.sort(key=lambda x:x[0])

pairs = []
for b in blu:
    for r in red:
        if r[0] < b[0] and r[1] < b[1] and not r in pairs:
            pairs.append(r)
            break

print(len(pairs))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
rl = [list(map(int, input().split())) for i in range(n)]
bl = [list(map(int, input().split())) for i in range(n)]

rl.sort(key=lambda x: x[1], reverse=True)
bl.sort(key=lambda y: y[0])

ans=0

# 貪欲
# それぞれの青に対してペアになれる赤のうち、yが最大のものを選んでいく
for b in bl:
    for r in rl:
        if r[0] < b[0] and r[1] < b[1]:
            rl.remove(r)
            ans += 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))
for i in range(n):
    c,d = map(int,input().split())
    blue.append((c,d))
    
red_sorted = sorted(red,reverse=True)
blue_sorted = sorted(blue,key=lambda x: x[1])

count = 0
check = []
for i in red_sorted:
    for j,k in enumerate(blue_sorted):
        if (i[0] < k[0]) and (i[1] < k[1]):
            blue_sorted.pop(j)
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
r = sorted([list(map(int, input().split())) for i in range(n)], reverse=True)
b = sorted([list(map(int, input().split())) for i in range(n)])

rd = set()

for i in range(n):
    p = []
    for j in range(n):
        if j in rd:
            continue
        if b[i][0] > r[j][0] and b[i][1] > r[j][1]:
            p.append(r[j] + [j])
    if len(p) > 0:
        p.sort(key=lambda x: x[1], reverse=True)
        rd.add(p[0][2])
print(len(rd))

Submission status: Accepted

Solution code:
n = int(input())

redPoints = []
bluePoints = []

for i in range(n):
    redPoints.append([int(x) for x in input().split(" ")])
for i in range(n):
    bluePoints.append([int(x) for x in input().split(" ")])
# deletation
for bluePoint in bluePoints:
    if bluePoint[0] == 0 or bluePoint[1] == 0:
        bluePoints.remove(bluePoint)

result = 0
bluePoints = sorted(bluePoints)
redPoints = sorted(redPoints, key=lambda x: -x[1])
for bluePoint in bluePoints:
    for redPoint in redPoints:
        # print("See:", redPoint, bluePoint)
        if redPoint[0] < bluePoint[0] and redPoint[1] < bluePoint[1]:
            result += 1
            redPoints.remove(redPoint)
            # print(redPoint, " is inner of ", bluePoint)
            break

print(result)

Submission status: Accepted

Solution code:
N = int(input())
red = sorted([list(map(int,input().split())) for _ in range(N)], key = lambda x:-x[1])
blue = sorted([list(map(int,input().split())) for _ in range(N)])

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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(reverse=True, key=itemgetter(1))
B.sort()

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

Submission status: Accepted

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

count = 0
B = sorted(B)
for b in B:
    y_max = -1
    for i,r in enumerate(R):
        if r[0]<b[0] and r[1]<b[1] and y_max < r[1]:
            y_max = r[1]
            r_num = i
    if y_max != -1:
        R.pop(r_num)
        count += 1
print(count)