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:
# ２部マッチング
# 最大流
# Ford-Fulkerson
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]

# -1: source, 2N: sink
edge = {-1: {}, 2 * N: {}}
for i, a in enumerate(A):
    edge[i] = {}
    edge[-1][i] = 1
    for j, b in enumerate(B):
        j += N
        if j not in edge:
            edge[j] = {}
        edge[j][2 * N] = 1
        if a[0] < b[0] and a[1] < b[1]:
            edge[i][j] = 1

visited = [False] * (2 * N + 2)
def find_route(start, goal, bottleneck):
    global visited
    visited[start] = True
    if start == goal:
        return bottleneck
    for to in edge[start]:
        if visited[to] or edge[start][to] <= 0:
            continue
        flow = find_route(to, goal, min(bottleneck, edge[start][to]))
        if flow > 0:
            edge[start][to] = edge[start].get(to, 0) - flow
            edge[to][start] = edge[to].get(start, 0) + flow
            return flow
    return 0

ans = 0
while True:
    visited = [False] * (2 * N + 2)
    flow = find_route(-1, 2 * N, float('inf'))
    if flow == 0:
        break
    ans += flow
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
for i in range(N):
    red.append(list(map(int, input().split()))+[0])
for i in range(N):
    blue.append(list(map(int, input().split())))
blue.sort()
res = 0
for x in blue:
    tar = [-1, -1, 0]
    for y in red:
        if y[2] == 0 and y[0] < x[0] and y[1] < x[1] and y[1] > tar[1]:
            tar = y

    if tar[0] >= 0:
        res += 1
        for i in range(N):
            if red[i] == tar:
                red[i][2] = 1
                break

print(res)

Submission status: Accepted

Solution code:
N=int(input())
r=[(0,0) for i in range(N)]
b=[(0,0) for i in range(N)]

for i in range(N):
    x,y=map(int,input().split())
    r[i]=(x,y)
for i in range(N):
    x,y=map(int,input().split())
    b[i]=(x,y)
b.sort()
ru=[0 for i in range(N)]
ans=0
for i in range(N):
    k=-1
    for j in range(N):
        if b[i][0]>r[j][0] and b[i][1]>r[j][1]:
            if k==-1 and ru[j]==0:
                k=j
            elif r[k][1]<r[j][1] and ru[j]==0:
                k=j
    if k!=-1:
        ru[k]=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

def main():
  N = read()
  rs = []; bs = []
  for i in range(N):
    a, b = reads()
    rs.append((a, b))
  for i in range(N):
    a, b = reads()
    bs.append((a, b))
  
  bi = bipmatch(2 * N)
  for i, j in product(range(N), range(N)):
    if rs[i][0] < bs[j][0] and rs[i][1] < bs[j][1]:
      bi.add_edge(i, N+j)
  ans = bi.count_match()
  print(ans)

class bipmatch:
  def __init__(self, N):
    self.size = N
    self.edges = [[] for _ in range(N)]

  def add_edge(self, u, v):
    self.edges[u].append(v)
    self.edges[v].append(u)

  def dfs(self, match, used, u):
    N = self.size; edges = self.edges
    used[u] = True
    for v in edges[u]:
      w = match[v]
      if w < 0 or not used[w] and self.dfs(match, used, w):
        match[u], match[v] = v, u
        return True
    return False

  def count_match(self):
    N = self.size; edges = self.edges
    res = 0; match = [-1] * N
    for v in range(N):
      if match[v] < 0:
        used = [0] * N
        if self.dfs(match, used, v):
          res += 1
    return res

main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

red_list = []
blue_list = []

for _ in range(N):
    red_list.append(list(map(int, input().split())))
for _ in range(N):
    blue_list.append(list(map(int, input().split())))
red_list.sort(key = lambda x : x[1], reverse = True)
blue_list.sort(key = lambda x : x[0])

count = 0
for b in blue_list:
    for ri, r in enumerate(red_list):
        if b[0] > r[0] and b[1] > r[1]:
            count += 1
            del red_list[ri]
            break

print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
lesser = [list(map(int, input().split())) + [0] for _ in range(n)]
greater = [list(map(int, input().split())) for _ in range(n)]

g = sorted(greater, key=itemgetter(0))

ans = 0
for i in range(n):
	y_max = -1
	for j in range(n):
		if lesser[j][0] < g[i][0] and y_max < lesser[j][1] < g[i][1] and lesser[j][2] == 0:
			y_max = lesser[j][1]
			y_max_index = j

	if y_max != -1:
		ans += 1
		lesser[y_max_index][2] = 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n = f.read_int()
    r = [tuple(f.read_int_list()) for _ in xrange(n)]
    b = [tuple(f.read_int_list()) for _ in xrange(n)]

    ans = 0
    b.sort()
    for bi in b:
        cand = None
        for ri in r:
            if ri[0] > bi[0] or ri[1] > bi[1]: continue
            if cand is None:
                cand = ri
            else:
                if ri[1] > cand[1]: cand = ri
        if cand is not None:
            ans += 1
            r.remove(cand)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
red = []
blue = []
for _ in range(n):
    red.append(list(map(int, input().split())))
for _ in range(n):
    blue.append(list(map(int, input().split())))
red.sort(key=itemgetter(0), reverse=True)
blue.sort(key=itemgetter(1), reverse=False)
for i in range(n):
    for j in range(len(blue)):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            blue.pop(j)
            break
print(n-len(blue))

Submission status: Accepted

Solution code:
N = int(input())
reds = [list(map(int, input().split())) for i in range(N)]
blues = [list(map(int, input().split())) for i in range(N)]
reds.sort(key=lambda x: x[0], reverse=True)
blues.sort(key=lambda x: x[1])
red_used = []
blue_used = []

for red in reds:
    for blue in blues:
        if red in red_used or blue in blue_used:
            continue
        if red[0] < blue[0] and red[1] < blue[1]:
            red_used.append(red)
            blue_used.append(blue)

print(len(blue_used))

Submission status: Accepted

Solution code:
N = int(input())
ab = sorted([ tuple(map(int, input().split())) for x in range(N)], key=lambda x:x[1],reverse=True)
cd = sorted([ tuple(map(int, input().split())) for x in range(N)])
resultx = []
resulty = []
for xb, yb in list(cd):
    for xr, yr in list(ab):
        if (xr, yr) in resultx:
            continue
        if xr < xb and yr < yb:
            resultx.append((xr,yr))
            resulty.append((xb,yb))
            break

print(len(resultx))

Submission status: Accepted

Solution code:
n = int(input())
red  = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
red.sort
blue.sort()
ans = 0

for x, y in blue:
    correct = [z for z in red if (z[0] < x) & (z[1] < y)]
    if correct:
        correct.sort(key=lambda x:x[1])
        red.remove(correct[-1])
        ans += 1

print(ans)

Submission status: Accepted

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


R.sort(reverse=True, key=lambda k: k[1])
B.sort()

p = []
q = []
for c, d in B:
    for a, b in R:
        if (a, b) in p:
            continue
        if a < c and b < d:
            p.append((a, b))
            q.append((c, d))
            break

print(len(p))

Submission status: Accepted

Solution code:
import numpy as np

def check(r, b):
    return r[0] < b[0] and r[1] < b[1]

if __name__ == '__main__':
    N = int(input())
    RED = []
    BLUE = []
    flag = []
    for i in range(N):
        RED.append(list(map(int, input().split())))

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

    RED  = np.array(RED)
    BLUE = np.array(BLUE)

    args_b = np.argsort(BLUE[:,0])
    BLUE = BLUE[args_b]
    args_r = np.argsort(RED[:, 1])[::-1]
    RED  = RED[args_r]

    count = 0
    for b in BLUE:
        for i in range(len(RED[:, 0])):
            if RED[i, 0] < b[0] and RED[i, 1] < b[1]:
                count += 1
                RED = np.delete(RED, i, 0)
                break

    print(count)

Submission status: Accepted

Solution code:
def bigger(a, b):
    return a[0] > b[0] and a[1] > b[1]


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

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

ret = 0
ab_used, cd_used = [], []
for c in cd:
    for a in ab:
        if a in ab_used:
            continue
        if c in cd_used:
            break
        if bigger(c, a):
            ab_used.append(a)
            cd_used.append(c)
            ret += 1
            break

print(ret)

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

edge = { -1: {}, 2*N: {} }
for i, a in enumerate(A):
  edge[i] = {}
  edge[-1][i] = 1
  for j, b in enumerate(B):
    j += N
    if j not in edge:
      edge[j] = {}
    edge[j][2*N] = 1
    if a[0] < b[0] and a[1] < b[1]:
      edge[i][j] = 1

# Ford-Fulkerson (impl: DFS)
visited = [False] * (2*N+2)
def find_route(start, goal, bottleneck):
  global visited
  visited[start] = True
  if start == goal:
    return bottleneck
  for to in edge[start]:
    if visited[to] or edge[start][to] <= 0:
      continue
    flow = find_route(to, goal, min(bottleneck, edge[start][to]))
    if flow > 0:
      edge[start][to] = edge[start].get(to, 0) - flow
      edge[to][start] = edge[to].get(start, 0) + flow
      return flow
  return 0

ans = 0
while True:
  visited = [False] * (2*N+2)
  flow = find_route(-1, 2*N, float("inf"))
  if flow == 0:
    break
  ans += flow
print(ans)

Submission status: Accepted

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

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

reds = sorted(reds, key=lambda x: -x[1])
blues = sorted(blues, key=lambda x: x[0])

res = 0
for i, b in enumerate(blues):
    for j, r in enumerate(reds):
        if r[0] < b[0] and r[1] < b[1]:
            res += 1
            reds.pop(j)
            break

print(res)

Submission status: Accepted

Solution code:
n = int(input())
ab = [[0,0] for i in range(n)]
cd = [[0,0] for i in range(n)]
for i in range(n):
    ab[i] = map(int, input().split())

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

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

#print(ab)

ab.sort(key=lambda coordinates:coordinates[1]*(-1))
#print(ab)

#print(cd)
cd.sort()
#print(cd)

count = 0
i=0
j=0

while len(cd) > 0:
    flag = 0
    for j in range(len(ab)):
        if cd[0][0] > ab[j][0] and cd[0][1] > ab[j][1]:
            flag = 1
            del(cd[0])
            del(ab[j])
            #print("j=",j)
            #print("ab=",ab)
            #print("cd=",cd)
            break
    if flag==0:
        del(cd[0])
    else:
        count += 1

print(count)

Submission status: Accepted

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

reds.sort(key=lambda x: x[1], reverse=True)
blues.sort()

done = [False] * N
ans = 0
for bx, by in blues:
    for i, (rx, ry) in enumerate(reds):
        if done[i]: continue
        if rx < bx and ry < by:
            ans += 1
            done[i] = True
            break

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([LI() for _ in range(n)], reverse=True)
    b = set([tuple(LI()) for _ in range(n)])
    r = 0
    for c in a:
        t = (-1, 10000)
        for d in b:
            if c[0] < d[0] and c[1] < d[1] and t[1] > d[1]:
                t = d
        if t != (-1, 10000):
            r += 1
            b.remove(t)

    return r


print(main())

Submission status: Accepted

Solution code:
def dfs(v):
    if was[v] == clr: return 0
    was[v] = clr
    for u in g[v]:
        if mt[u] == -1 or dfs(mt[u]):
            mt[u] = v
            return 1
    return 0

read = lambda: map(int, input().split())
n = int(input())
n2 = n * 2
a = [0] * n2
b = [0] * n2
g = [list() for i in range(n2)]
for i in range(n):
    a[i], b[i] = read()
for i in range(n):
    a[i+n], b[i+n] = read()
for i in range(n):
    for j in range(n, n2):
        if a[i] < a[j] and b[i] < b[j]:
            g[i].append(j)
            g[j].append(i)
mt = [-1] * n2
was = [0] * n2
clr = 1
ans = 0
for i in range(n):
    if dfs(i):
        ans += 1
        clr += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False

e = int(input())
edges = [set() for _ in range(e)]
matched = [-1] * e

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

for i in range(e):
    for j in range(e):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            edges[j].add(i)

print(sum(dfs(s, set()) for s in range(e)))

Submission status: Accepted

Solution code:
N = int(input())
ps = [tuple(map(int,input().split() + [i//N])) for i in range(2*N)]
ans = 0
unused_red_y = []
for x,y,c in sorted(ps):
    if c == 0:
        unused_red_y.append(y)
    else:
        found_i = found_ry = -1
        for i,ry in enumerate(unused_red_y):
            if ry > y: continue
            if found_ry < ry:
                found_ry = ry
                found_i = i
        if found_i >= 0:
            unused_red_y.pop(found_i)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import *
import random

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

n = readln()[0]
r = [0 for i in range(0,n)]
b = [0 for i in range(0,n)]

for i in range(0,n):
    r[i] = readln()


for i in range(0,n):
    b[i] = readln()

r = sorted(r)
b = sorted(b)

ans = 0
for blue in b:
    y = -1
    for red in r:
        if red[0] > blue[0]:
            break
        if red[1] < blue[1] and red[1] > y:
            y = red[1]
    if y > -1:
        ans = ans + 1
        for i in range(0,n):
            if r[i][0] < blue[0] and r[i][1] == y:
                r[i][1] = 10000000000
                break

print(ans)

Submission status: Accepted

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

def fulkerson(graph, src, sink):
    n = len(graph)

    matrix = [[0]*n for i in range(n)]
    bothDirGraph = [[] for i in range(n)]

    for nodeId, edges in enumerate(graph):
        for nodeId2, flowLimit in edges:
            matrix[nodeId][nodeId2] = flowLimit
            bothDirGraph[nodeId].append(nodeId2)
            bothDirGraph[nodeId2].append(nodeId)

    while True:
        path = findPath(bothDirGraph, matrix, src, sink)

        if path == None:
            break

        v = min(matrix[path[i]][path[i+1]] 
                for i in range(len(path)-1))

        for i in range(len(path)-1):
            node1 = path[i]
            node2 = path[i+1]
            
            matrix[node1][node2] -= v
            matrix[node2][node1] += v

    return (sum(c for _, c in graph[src]) - 
            sum(c for c in matrix[src]))


def findPath(bothDirGraph, matrix, src, sink):
    prevs = [None]*len(matrix)
    q = set([src])
    prevs[src] = src

    while len(q) > 0:
        node = q.pop()

        for nextNode in bothDirGraph[node]:
            if prevs[nextNode] == None and matrix[node][nextNode] > 0:
                prevs[nextNode] = node
                
                if nextNode == sink:
                    path = []
                    pathNode = sink

                    while pathNode != src:
                        path.append(pathNode)
                        pathNode = prevs[pathNode]

                    path.append(src)
                    return list(reversed(path))

                q.add(nextNode)

    return None
                    

def main():
    N = int(input())
    graph = [[] for i in range(2*N+2)]
    
    for i in range(N):
        graph[0].append(((i+1)*2, 1))
        graph[(i+1)*2+1].append((1, 1))

    p1s = [tuple(map(int, input().split())) for i in range(N)]
    p2s = [tuple(map(int, input().split())) for i in range(N)]

    for i1, p1 in enumerate(p1s):
        for i2, p2 in enumerate(p2s):
            if p1[0] < p2[0] and p1[1] < p2[1]:
                graph[(i1+1)*2].append(((i2+1)*2+1, 1))

    print(fulkerson(graph, 0, 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
r=[]
b=[]
G=[[] for i in range(n*2+2)]

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

def dfs(v,t,f,used):
	if v==t:
	  return f
	used[v] = 1
	for i in range(len(G[v])):
		e = G[v][i]
		if used[e[0]]==0 and e[1]>0:
			d = dfs(e[0], t, min(f,e[1]),used);
			if d > 0:
				e[1] -= d;
				
				G[e[0]][e[2]][1] += d
                                
				return d
			
		
	
	return 0


def max_flow(s,t):
        
	flow = 0
	while(1):
		used=[0 for i in range(2*n+2)]
		f = dfs(s, t, float("inf"),used)
		if f==0:
			return flow
		
		flow += f
	
for i in range(n):
 r.append(i2())
for i in range(n):
 b.append(i2())
for i in range(n):
 add_edge(0,i+1,1)
for i in range(n):
 add_edge(n+1+i,2*n+1,1)
for i in range(n):
 for j in range(n):
   if r[i][0]<b[j][0] and r[i][1]<b[j][1]:
       add_edge(1+i,n+1+j,1)
print(max_flow(0,2*n+1))

Submission status: Accepted

Solution code:
import heapq

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

# both.sort(key=lambda xyz: xyz[1])
both.sort(key=lambda xyz: xyz[0])

# According to the heapq documentation, the way to customize the heap order is
# to have each element on the heap to be a tuple, with the first tuple element
# being one that accepts normal Python comparisons.
red_heap = []
ans = 0
for xyz in both:
    y = xyz[1]
    if xyz[2]:
        heapq.heappush(red_heap, (-y, xyz))
    else:
        popped = []
        while red_heap:
            r = heapq.heappop(red_heap)
            if r[1][1] < y:
                ans += 1
                break
            popped.append(r)
        for r in popped:
            heapq.heappush(red_heap, r)

print(ans)

Submission status: Accepted

Solution code:
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
Q = [list(map(int, input().split())) for i in range(N)]
dinic = Dinic(2*N+2)
for i in range(N):
    dinic.add_edge(0, 2+i, 1)
    dinic.add_edge(2+N+i, 1, 1)
for i in range(N):
    a, b = P[i]
    for j in range(N):
        c, d = Q[j]
        if a < c and b < d:
            dinic.add_edge(2+i, 2+N+j, 1)
print(dinic.max_flow(0, 1))

Submission status: Accepted

Solution code:
n=int(input())
r=[list(map(int,input().split())) for i in range(n)]
b=[list(map(int,input().split())) for i in range(n)]
b.sort()
for i in range(n):
    target=-1
    for j in range(len(r)):
        if r[j][0]<b[i][0] and r[j][1]<b[i][1]:
            if target==-1 or r[j][1]>r[target][1]:
                target=j
    if target!=-1:
        del r[target]
print(n-len(r))

Submission status: Accepted

Solution code:
from operator import itemgetter

if __name__ == '__main__':
    N = int(input())
    plots = []
    for i in range(2 * N):
        x, y = map(int, input().split())
        if i < N:
            plots.append([x, y, "r"])
        else:
            plots.append([x, y, "b"])

    plots = sorted(plots, key=itemgetter(0))

    t_set = set()
    ans = 0
    for x, y, c in plots:
        if c == "r":
            t_set.add(y)
            continue

        if len(t_set) == 0 or y < min(t_set):
            continue

        ans += 1
        del_y = 0
        for tmp in t_set:
            if y > tmp > del_y:
                del_y = tmp

        t_set.remove(del_y)

    print(ans)

Submission status: Accepted

Solution code:
n = input()
a = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], key = lambda x: x[1], reverse = True)
b = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], key = lambda x: x[0])
cnt = 0
for j in b:
    for i in a:
        if i[0] < j[0] and i[1] < j[1] and i[2] and j[2]:
            cnt, i[2], j[2] = cnt + 1, 0, 0
print cnt

Submission status: Accepted

Solution code:
n = int(input())
abs_ = [tuple(map(int, input().split())) for _ in range(n)]
cds = [tuple(map(int, input().split())) for _ in range(n)]

ab_to = [set() for _ in range(len(abs_))]
cd_from = [set() for _ in range(len(cds))]

ab_pair = [-1 for _ in range(len(abs_))]
cd_pair = [-1 for _ in range(len(cds))]

def dfs(j, visited):
    i = cd_pair[j]
    if i == -1:
        return [j]
    visited.add(j)
    for k in ab_to[i]:
        if k in visited:
            continue
        #visited.add(k)
        r = dfs(k, visited)
        if r is not None:
            r.append(j)
            return r

for i, (a, b) in enumerate(abs_):
    for j, (c, d) in enumerate(cds):
        if a < c and b < d:
            ab_to[i].add(j)
            cd_from[j].add(i)
            """
            if ab_pair[i] == -1 and cd_pair[j] == -1:
                ab_pair[i] = j
                cd_pair[j] = i
            """

# print(ab_pair)
# print(cd_pair)

continue_ = True
while continue_:
    continue_ = False
    for i, (a, b) in enumerate(abs_):
        if ab_pair[i] == -1:
            visited = set()
            for cand in ab_to[i]:
                route = dfs(cand, visited)
                #print(route)
                if route is not None:
                    continue_ = True
                    for k in range(len(route)-1):
                        a = cd_pair[route[k+1]]
                        ab_pair[a], cd_pair[route[k]] = route[k], a
                    ab_pair[i], cd_pair[route[-1]] = route[-1], i
                    break

# print(ab_pair)
print(sum(1 for p in ab_pair if p != -1))

Submission status: Accepted

Solution code:
import numpy as np
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)]

points = red + blue
points.sort()
temp = []
ans = 0
for p in points:
    if p in red:
        temp.append(p)
    else:
        temp.sort(key=lambda x: x[1], reverse=True)
        for t in temp:
            if t[0] < p[0] and t[1] < p[1]:
                temp.remove(t)
                ans += 1
                break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = sorted(tuple(map(int, input().split())) for _ in range(n))
cd = sorted(tuple(map(int, input().split())) for _ in range(n))
for c, d in cd:
    i = -1
    y = -1
    for j, (a, b) in enumerate(ab):
        if a < c and b < d and b > y:
            i = j
            y = b
    if i != -1:
        del ab[i]
print(n - len(ab))

Submission status: Accepted

Solution code:
# C
N = int(input())

red_list = []
blue_list = []

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

for _ in range(N):
    x, y = map(int, input().split())
    blue_list.append([x, y])
    
GR = dict()
GB = dict()

for i in range(N):
    GR[i+1] = [0, [], 0]
    GB[i+1] = [0, [], 0]

for i in range(N):
    for j in range(N):
        if red_list[i][0] < blue_list[j][0] and red_list[i][1] < blue_list[j][1]:
            GR[i+1][1].append(j+1)
            GB[j+1][1].append(i+1)
            
def find_path(GR_, GB_, N):
    GR = GR_.copy()
    GB = GB_.copy()

    done_red = [0]*(N+1)
    can_red = [0]*(N+1)
    done_blue = [0]*(N+1)

    # start from RED
    for i in range(1, N+1): 
        if GR[i][0] == 0:
            can_red[i] = 1
        GR[i][2] = -1
        GB[i][2] = -1

    while True:

        go_flg = 0
        for i in range(1, N+1):
            if can_red[i] == 1 and done_red[i] == 0:
                go_flg = 1

        if go_flg == 0:
            return []

        for i in range(1, N+1): 
            if can_red[i] == 1 and done_red[i] == 0:
                done_red[i] = 1
                for j in GR[i][1]:
                    if done_blue[j] == 0:
                        GB[j][2] = i
                        done_blue[j] = 1
                        if GB[j][0] != 0:
                            can_red[GB[j][0]] = 1
                            GR[GB[j][0]][2] = j
                        else:
                            # found
                            res_list = [j, i]
                            while GR[res_list[-1]][2] > 0:
                                j = GR[res_list[-1]][2]
                                i = GB[j][2]
                                res_list.append(j)
                                res_list.append(i)
                            return res_list
                        
# set initial path
res = 0
for i in range(1, N+1):
    for j in GR[i][1]:
        if GB[j][0] == 0:
            GR[i][0] = j
            GB[j][0] = i
            res += 1
            break

while True:
    new_path = find_path(GR, GB, N)
    if len(new_path) == 0:
        break
    else:
        for l in range(len(new_path) // 2):
            j, i = new_path[2*l], new_path[2*l+1]
            GB[j][0] = i
            GR[i][0] = j
        res += 1

print(res)