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:
from math import ceil
from operator import itemgetter

def main():
    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 = itemgetter(1))
    AB.sort(key = itemgetter(0))
    CD.sort( key = itemgetter(0))
    CD.sort(key = itemgetter(1))

    ans = 0
    used = [False]*N
    for i in range(N):
        c,d = CD[i]
        for j in range(N):
            a,b = AB[N - j - 1]
            if not(used[N - j - 1]) and a <= c and b <= d:
                ans += 1
                used[N - j - 1] = True
                break
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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)]
alr = [False for i in range(N)]
ab.sort()
cd.sort()
count = 0
for c,d in cd:
    maxi = -1
    maxb = -1
    for i in range(N):
        if alr[i]:
            continue
        a,b = ab[i][0],ab[i][1]
        if a < c:
            if b < d:
                if maxb < b:
                    maxb = b
                    maxi = i
        else:
            break
    if maxi != -1:
        alr[maxi] = True
print(alr.count(True))

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

ans = 0
for rx,ry in R:
    for bx,by in B:
        # print(rx,ry,bx,by)
        if rx<bx and ry<by:
            # print("ok")
            ans += 1
            B.remove([bx,by])
            break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = [tuple(map(int, input().split())) for i in range(N)]
blue = [tuple(map(int, input().split())) for i in range(N)]

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

used = [0]*N

ans = 0
for bx, by in blue:
    for ri in range(N):
        if used[ri] == 1:
            continue
        rx, ry = red[ri]
        if rx < bx and ry < by:
            used[ri] = 1
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from operator import itemgetter

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[int(x) for x in input().split()] for _ in range(N)]
    CD = [[int(x) for x in input().split()] for _ in range(N)]

    AB.sort(key=itemgetter(1), reverse=True)
    CD.sort(key=itemgetter(0))

    ans = 0
    used = set()
    for i, cd in enumerate(CD):
        c, d = cd[0], cd[1]
        for j, ab in enumerate(AB):
            if j in used:
                continue
            a, b = ab[0], ab[1]
            if c > a and d > b:
                used.add(j)
                ans += 1
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
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()
cd.sort()

g = defaultdict(list)

for c,d in cd:
    for a,b in ab:
        if a < c and b < d:
            g[c].append(a)
            g[a].append(c)

used = [False]*(2*N)
match = [-1]*(2*N)

def dfs(v):
    used[v] = True
    for nv in g[v]:
        nnv = match[nv]
        if nnv == -1:
            match[v] = nv
            match[nv] = v
            return True
        elif not used[nnv] and dfs(nnv):
            match[v] = nv
            match[nv] = v
            return True
    return False

ans = 0
for i in range(2*N):
    if match[i] == -1:
        used = [False]*(2*N)
        if dfs(i):
            ans += 1
    #print(match)

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
Red = [list(map(int,input().split())) for _ in range(N)] #赤
Blue = [list(map(int,input().split())) for _ in range(N)] #青

Red1 = sorted(Red, key=itemgetter(1),reverse = True)
Blue1 = sorted(Blue, key=itemgetter(0)) #ここが違った
cnt = 0

for i in range(N): 
    for j in range(N):
        if (Blue1[i][0] > Red1[j][0]) and (Blue1[i][1] > Red1[j][1]):
            cnt+=1
            Red1[j] = [500,500] #これがなかった
            #print(B1[i],A1[j])
            break #これがなかった
print(cnt)

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()
cd.sort()
cnt = 0
for i, j in cd:
	x = []
	for k,l in ab:
		if k < i and l < j:
			x.append([k,l])
	if len(x) > 0:
		cnt += 1
		xx = sorted(x, key=lambda x:x[1])
		ab.remove(xx[-1])
print (cnt)

Submission status: Accepted

Solution code:
N = int(input())
Red = [0] * N
Blue = [0] * N
for j in range(N):
    Red[j] = [0] * 2
    Red[j][0], Red[j][1] = map(int, input().split())
for k in range(N):
    Blue[k] = [0] * 2
    Blue[k][0], Blue[k][1] = map(int, input().split())
Blue = sorted(Blue)
Red = sorted(Red)
ans = 0
for i in range(N):
    kouho = -1
    blue_x = Blue[i][0]
    blue_y = Blue[i][1]
    kouho_y = -1
    for p in range(len(Red)):
        if blue_x > Red[p][0]:
            if kouho_y < Red[p][1] <blue_y:
                kouho_y = Red[p][1]
                kouho = p
        else:
            continue
    if kouho >= 0:
        ans += 1
        del Red[kouho]

print(ans)
#print(Red)
#print(Blue)

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()
d,ans=dict(),0
for i in range(n):
  cnt=-1
  ok=False
  for j in range(n):
    if j not in d:
      if b[i][0]>r[j][0] and b[i][1]>r[j][1]:
        if r[j][1]>cnt:
          cnt=r[j][1]
          k=j
          ok=True
  if ok:
    ans+=1
    d[k]=0
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # x 降順
    ab.sort(key=lambda x: x[0], reverse=True)
    # y 昇順
    cd.sort(key=lambda x: x[1])
    ans = 0
    for bx, by in cd:
        for rx, ry in ab:
            if rx < bx and ry < by:
                ab.remove((rx, ry))
                ans += 1
                break
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort()
    ans = 0
    for bx, by in cd:
        for rx, ry in ab:
            if rx < bx and ry < by:
                ab.remove((rx, ry))
                ans += 1
                break
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=lambda x:x[1], reverse=True)
    # x 昇順
    cd.sort()
    ans = 0
    for bx, by in cd:
        for rx, ry in ab:
            if rx < bx and ry < by:
                ab.remove((rx, ry))
                ans += 1
                break
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=lambda x:x[1], reverse=True)
    # x 昇順
    cd.sort()
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ((rx, ry), d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort()
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ((rx, ry), d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    ans = 0
    for bx, by in cd:
        for rx, ry in ab:
            if rx < bx and ry < by:
                ab.remove((rx, ry))
                ans += 1
                break
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ((rx, ry), d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [[int(j) for j in input().split()] for i in range(N)]
    cd = [[int(j) for j in input().split()] for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ((rx, ry), d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [[int(j) for j in input().split()] for i in range(N)]
    cd = [[int(j) for j in input().split()] for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        for k, ([rx, ry], d) in enumerate(zip(ab, done)):
            if not d and rx < bx and ry < by:
                done[k] = True
                break
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [tuple(int(j) for j in input().split()) for i in range(N)]
    cd = [tuple(int(j) for j in input().split()) for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        i = 0
        for rx, ry in ab:
            if not done[i] and rx < bx and ry < by:
                done[i] = True
                break
            i += 1
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    N = int(input())
    ab = [[int(j) for j in input().split()] for i in range(N)]
    cd = [[int(j) for j in input().split()] for i in range(N)]
    # y 降順
    ab.sort(key=itemgetter(1), reverse=True)
    # x 昇順
    cd.sort(key=itemgetter(0))
    # ペアになった赤
    done = [False] * N
    for bx, by in cd:
        i = 0
        for rx, ry in ab:
            if not done[i] and rx < bx and ry < by:
                done[i] = True
                break
            i += 1
    print(sum(done))
    return


main()

Submission status: Accepted

Solution code:
import copy

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
b = [list(map(int, input().split())) for _ in range(N)]

chk = [0] * (2 * N)
cpchk =[]
pare = [-1] * (2 * N)
ans = 0

d = [[] for _ in range(2 * N)]
for i in range(N):
    for j in range(N):
        if a[i][0] < b[j][0] and a[i][1] < b[j][1]:
            d[i].append(j + N), d[j + N].append(i)

def dfs(v):
    cpchk[v] = 1
    for i in range(len(d[v])):
        u = d[v][i]
        w = pare[u]
        if w < 0 or cpchk[w] == 0 and dfs(w):
            pare[v] = u
            pare[u] = v
            return True
    return False

def bipartite_mattinc():
    global ans
    global cpchk
    for i in range(2 * N):
        if pare[i] < 0:
            cpchk = copy.deepcopy(chk)
            if dfs(i):
                ans += 1
    return ans

print(bipartite_mattinc())

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
memo = [0]*N
ans = 0

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

for i in range(N):
  bx,by = blue[i]
  for j in range(N):
    rx,ry = red[j]
    if memo[j] == 0 and rx<=bx and ry<=by:
      memo[j] = 1
      ans += 1
      break
print(ans)

Submission status: Accepted

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


for i in range(1,n):
    for j in range(i-1,-1,-1):
        if r[j+1][1] < r[j][1]:
            r[j+1], r[j] = r[j], r[j+1] 

for i in range(1,n):
    for j in range(i-1,-1,-1):
        if b[j+1][0] < b[j][0]:
            b[j+1], b[j] = b[j], b[j+1]

ans = 0
for i in range(n-1, -1, -1):
    for j in range(n):
        if (r[i][0] < b[j][0]) and (r[i][1] < b[j][1]):
            ans += 1
            b[j][0] = -1
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[0 for i in range(2)]for j in range(n)]
b = [[0 for i in range(2)]for j in range(n)]

for i in range(n):
    a[i][0] , a[i][1] = map(int, input().split())
for i in range(n):
    b[i][0] , b[i][1] = map(int, input().split())
    
ans = 0
    
a.sort(key=lambda x: x[1] , reverse = True)
b.sort(key=lambda x: x[0])

for j in b:
    for i in a:
        if i[0] < j[0] and i[1] < j[1]:
            a.remove(i)
            ans += 1
            break
            
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(N):
    a = ab[i][0]
    b = ab[i][1]
    for j in range(N):
        if cd[j][2] == True:
            continue 
        c = cd[j][0]
        d = cd[j][1]
        if a<c and b<d:
            ans += 1
            cd[j][2] = True
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
red = []
blue = []
chosen = [0]*N
ans = 0
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.sort(key=lambda x:x[1],reverse=True)
blue.sort(key=lambda x:x[0])

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 chosen[j] == 0:
      chosen[j] = 1
      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):
  a, b = map(int, input().split())
  BLUE.append((a, b))

BLUE.sort(key=lambda x: x[0])
RED.sort(key=lambda x: -x[1])


red_selected = set()
blue_selected = set()
for i in range(N):
  c, d = BLUE[i]
  
  for j in range(N):
    a, b = RED[j]
    if a < c and b < d and j not in red_selected and i not in blue_selected:
      red_selected.add(j)
      blue_selected.add(i)

print(len(red_selected))

Submission status: Accepted

Solution code:
n = int(input())
red_point = []
blue_point = []

for _ in range(n):
    x, y = map(int, input().split())
    red_point.append((x, y))

for _ in range(n):
    x, y = map(int, input().split())
    blue_point.append((x, y))

red_point = sorted(red_point, key = lambda x: x[1], reverse = True)
blue_point.sort()

ans = 0

for i in range(n):
    for j in range(len(red_point)):
        if blue_point[i][0] > red_point[j][0]:
            if blue_point[i][1] > red_point[j][1]:
                ans += 1
                del red_point[j]
                break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = []
cd = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append([a, b])
for _ in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])
cd.sort()
ab.sort(reverse=True, key=lambda x:x[1])
tableA = [False for _ in range(n)]
tableB = [False for _ in range(n)]
ans = 0
for b in range(n):
    for r in range(n):
        if tableA[r] is True or tableB[b] is True:
            continue
        if cd[b][0]>ab[r][0] and cd[b][1]>ab[r][1]:
            tableA[r] = True
            tableB[b] = True
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
red=[-1]*(n*2)
blue=[-1]*(n*2)
ans=0

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

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

for i in range(0,n*2):
    if blue[i]>=0:
        k=-1
        for j in range(0,i):
            if red[j]>=0 and red[j]<blue[i]:
                if k<0 or red[k]<red[j]:
                    k=j
        if k>=0:
            red[k]=-1
            ans+=1
            # print(k,i)

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque

n = int(input())
ab = deque(sorted((list(map(int, input().split())) for _ in range(n)), key=itemgetter(1),reverse=True))
cd = sorted((list(map(int, input().split())) for _ in range(n)), key=itemgetter(0))

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from operator import itemgetter

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
cd.sort()

m = defaultdict(lambda: [])
for i in range(n):
    for j in range(n):
        a,b = ab[i]
        c,d = cd[j]
        if a<c and b<d:
            m[j].append([i,a,b])

used = set()
res = 0
for j in range(n):
    if len(m[j])>0:
        l = sorted(m[j],key=itemgetter(2),reverse=True)
        for i,_,_ in l:
            if i not in used:
                used.add(i)
                res += 1
                break
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ab = []
cd = []
for _ in range(N):
    ab.append([int(x) for x in input().split()])
for _ in range(N):
    cd.append([int(x) for x in input().split()])
ab_x = sorted(ab, reverse=True, key=lambda x:x[0])
ab_y = sorted(ab, reverse=True, key=lambda x:x[1])
cd_x = sorted(cd, key=lambda x:x[0])
cd_y = sorted(cd, key=lambda x:x[1])
ans = 0
for i in ab_x:
    for j in cd_x:
        if i[0] < j[0] and i[1] < j[1]:
            ans += 1
            cd_x.remove(j)
            break
cnt = 0
for i in ab_y:
    for j in cd_y:
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
            cd_y.remove(j)
            break
temp = max(ans, cnt)
ab_x = sorted(ab, reverse=True, key=lambda x:x[0])
ab_y = sorted(ab, reverse=True, key=lambda x:x[1])
cd_x = sorted(cd, key=lambda x:x[0])
cd_y = sorted(cd, key=lambda x:x[1])
ans = 0
for i in ab_x:
    for j in cd_y:
        if i[0] < j[0] and i[1] < j[1]:
            ans += 1
            cd_y.remove(j)
            break
cnt = 0
for i in ab_y:
    for j in cd_x:
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
            cd_x.remove(j)
            break
print(max(temp, ans, cnt))

Submission status: Accepted

Solution code:
import bisect


n = int(input())
dots = []

for _ in range(n):
    a, b = map(int, input().split())
    dots.append([a, b, 0])

for _ in range(n):
    c, d = map(int, input().split())
    dots.append([c, d, 1])

dots.sort(reverse=True)

blues = []
count = 0
for x, y, color in dots:
    if color == 1:
        bisect.insort(blues, y)
    else:
        pair_idx = bisect.bisect_left(blues, y)
        if pair_idx == len(blues):
            continue
        else:
            count += 1
            blues.pop(pair_idx)

print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=itemgetter(1), reverse=True)
CD = [tuple(map(int, input().split())) for _ in range(N)]
CD.sort(key=itemgetter(0))
use = [False] * N
for a, b in AB:
    for i, (c, d) in enumerate(CD):
        if a < c and b < d and not use[i]:
            use[i] = True
            break
print(sum(use))

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

#print(AB)
#print(CD)

ans = 0

for i in range(N-1,-1,-1):
    ab = AB[i]
    li = []
    for cd in CD:
        if ab[0] < cd[0] and ab[1] < cd[1]:
            li.append(cd)
    li.sort(key=lambda x: x[1])
    if len(li) != 0:
        CD.remove(li[0])
        ans += 1
print(ans)

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

#print(AB)
#print(CD)

ans = 0

for cd in CD:
    li = []
    for ab in AB:
        if ab[0] < cd[0] and ab[1] < cd[1]:
            li.append(ab)
    li.sort(key=lambda x: x[1])
    if len(li) != 0:
        AB.remove(li[-1])
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    red = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    blue = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    
    red.sort(key=lambda x: x[1], reverse=True)
    blue.sort()
    
    for bp in blue:
        bx, by = bp
        for i, rp in enumerate(red):
            rx, ry = rp
            if rx < bx and ry < by:
                del red[i]
                break
    
    ans = N - len(red)
    print(ans)

solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    q = LIR(n)
    s = [(p[i][0],p[i][1],0) for i in range(n)]+[(q[i][0],q[i][1],1) for i in range(n)]
    s.sort()
    q = []
    ans = 0
    for x,y,i in s:
        if not i:
            q.append(y)
            q.sort()
        else:
            j = bisect.bisect_left(q,y)-1
            if j >= 0:
                q.pop(j)
                ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

N = int(input())
X = []
Y = []

for i in range(N):
  a, b = map(int, input().split())
  X.append((a, b))

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


X.sort(key=lambda x: -x[1])
Y.sort(key=lambda x: x[0])

B = []
result = 0

for x in range(N):
  red = list(map(int, X[x]))

  for y in range(N):
    blue = list(map(int, Y[y]))
    if y in B:
      continue
    if red[0] < blue[0] and red[1] < blue[1]:
      result += 1
      B.append(y)
      break
  
print(result)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l1=[LI() for _ in range(n)]
  l1.sort()
  l2=[LI() for _ in range(n)]
  l2.sort()

  check=[False for _ in range(n)]

  ans=0
  ans_list=[]
  for c,d in l2:
    _i=inf
    _b=-inf
    for i,[a,b] in enumerate(l1):
      if check[i]:
        continue

      if a<c and b<d:
        if _b<b:
          _i=i
          _b=b

    if _i!=inf:
      check[_i]=True
      ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
N = int(input())
reds = [tuple(map(int, input().split())) for _ in range(N)]
blues = [tuple(map(int, input().split())) for _ in range(N)]
reds.sort(key=lambda x: x[1], reverse=True)
blues.sort(key=lambda x: x[0])
ans = 0
for b in blues:
    for i, r in enumerate(reds):
        if b[0] > r[0] and b[1] > r[1]:
            ans += 1
            del reds[i]
            break
print(ans)

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:
"""
参考：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())