Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All input values are integers.

1 \leq N \leq 100

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum number of friendly pairs.

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

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

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



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


Sample output:
2

Submission status: Accepted

Solution code:
N = input()

B = [map(int,raw_input().split()) for i in range(N)]

A = [map(int,raw_input().split()) for i in range(N)]


A.sort()
B.sort()

for i in A:
    maxy = -1
    for j in B:
        if i[0] > j[0]:
            if maxy < j[1] and i[1] > j[1]:
                maxy = j[1]
                memory = j
        else:
            break
    if maxy != -1:
        B.remove(memory)

print len(A)-len(B)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import queue

class Dinic:
    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)


N = int(input())
A = [] #R_x
B = [] #R_y
C = [] #B_x
D = [] #B_y

for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(N):
    c,d = map(int, input().split())
    C.append(c)
    D.append(d)

#Rは2～N+1、BはN+2～2N+1
s = 0
e = 1
r_top = 2
b_top = N+2

dinic = Dinic(2 + 2*N)
for i in range(N):
    dinic.add_edge(s, r_top+i, 1)
    for j in range(N):
        if ((A[i] < C[j]) & (B[i] < D[j])):
            dinic.add_edge(r_top+i, b_top+j, 1)
            #print(i, j)
    dinic.add_edge(b_top+i, e, 1)

f = dinic.max_flow(s, e)

print(f)

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)]
blue=sorted(blue, key=lambda x:x[0])
ans=0 
for b in blue:
    for r in sorted([r_ for r_ in red if r_[0]<b[0]], key=lambda x:x[1], reverse = True):
        if r[1]<b[1]:
            ans+=1
            red.pop(red.index(r))
            break
print(ans)

Submission status: Accepted

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

def beFriend(red, blue):
    if red[0] < blue[0] and red[1] < blue[1]:
        return 1
    else:
        return 0

res = 0

for b in blue:
    for r in sorted([sr for sr in red if sr[0] < b[0]], key=lambda x:x[1], reverse = True):
        if beFriend(r, b):
            res += 1
            red.pop(red.index(r))
            break

print(res)

Submission status: Accepted

Solution code:
# encoding:utf-8

import numpy as np
import random
import copy

def select_ok(r_list,b_position):
    pass_list = []
    for i in range(len(r_list)):
        if r_list[i][0] < b_position[0] and r_list[i][1] < b_position[1]:
            pass_list.append(r_list[i])

    return pass_list



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

for i in range(n):
    position = list(map(int, input().split()))
    r.append(position)

for i in range(n):
    position = list(map(int, input().split()))
    b.append(position)

b_sorted = sorted(b,key=lambda x:x[0])
count = 0
for i in range(n):
    pairs = select_ok(r,b_sorted[i])
    if len(pairs) > 0:
        sorted_pairs = sorted(pairs,key=lambda x:x[1],reverse=True)
        # print(sorted_pairs)
        count += 1
        r.remove(sorted_pairs[0])

print(count)

# print(answer)

Submission status: Accepted

Solution code:
n = int(input())
Ps = [tuple(map(int, input().split())) for i in range(n)]
Qs = [tuple(map(int, input().split())) for i in range(n)]

Qs.sort()

ans = 0
for i in range(n):
    #l:PsのうちQs[i]とペアになれるものと、そのインデックス
    l = [(Ps[j], j)
         for j in range(len(Ps))
         if Ps[j][0] <= Qs[i][0] and Ps[j][1] <= Qs[i][1]]

    #なかったらなにもしない
    if l == []: continue

    # 条件を満たすもののうち最もy座標が大きいものとそのPsでのインデックス
    E = max(l, key=(lambda e: e[0][1]))
    del Ps[E[1]]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy


def main() -> None:
    n = int(input())
    red_points = [[int(r) for r in input().split()] for _ in range(n)]
    blue_points = [[int(b) for b in input().split()] for _ in range(n)]
    ans = 0

    for i in range(2):
        for j in range(2):
            red_points.sort(key=lambda x: x[i ^ 1])
            red_points.sort(key=lambda x: x[i])

            blue_points.sort(key=lambda x: -x[j ^ 1])
            blue_points.sort(key=lambda x: -x[j])

            rps = deepcopy(red_points)
            bps = deepcopy(blue_points)

            cnt = 0
            while len(rps) > 0:
                for k in range(len(bps) - 1, -1, -1):
                    if rps[-1][0] < bps[k][0] and rps[-1][1] < bps[k][1]:
                        rps.pop()
                        bps.pop(k)
                        cnt += 1
                        break
                    if k == 0:
                        rps.pop()
                ans = max(ans, cnt)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

count = 0
for i in range(n):
    for j in range(len(cd)):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
            count += 1
            del cd[j]
            break

print(count)

Submission status: Accepted

Solution code:
#解答確認後
n=int(input())
aa=[[int(i) for i in input().split()] for i in range(n)]
bb=[[int(i) for i in input().split()] for i in range(n)]

#print(aa)
#print(bb)

import operator
aa.sort(key=operator.itemgetter(1),reverse=True)
bb.sort()
  
#print(aa)
#print(bb)

answer=0
for b in bb:
  xb,yb=b
  for a in aa:
    xa,ya=a
    if xa<xb and ya<yb:
      answer=answer+1
      aa. remove (a)
      #print(aa)
      #print(bb)
      #print(answer)
      break
      
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
red = [list(map(int,input().split())) for i in range(N)]
# yについて降順にソート
red = sorted(red,key=lambda x:(-x[1]))
blue = [list(map(int,input().split())) for i in range(N)]
# xについて昇順にソート
blue = sorted(blue,key=lambda x:(x[0]))
cnt = 0
pair = []
for i in range(N):
    b_x = blue[i][0]
    b_y = blue[i][1]
    for j in range(N):
        index = 0
        for e in red:
            a_x = e[0]
            a_y = e[1]
            if b_x > a_x and b_y > a_y:
                cnt += 1
                pair.append([blue[i],e])
                del red[index]
                break
            index += 1
        else:
            continue
        break
print(cnt)

Submission status: Accepted

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

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

ans = 0

while blue:
    bA = blue.pop(0)
    for i in range(len(red)):
        rA = red[i]
        if bA[0]>rA[0] and bA[1]>rA[1]:
            red.pop(i)
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
red=sorted([list(map(int,input().split())) for i in range(N)], key=lambda x:-1*x[1])
blue=sorted([list(map(int,input().split())) for i in range(N)])
red = sorted(red, key = lambda x:x[1] * -1)
count=0
for i in red:
    for n,j in enumerate(blue):
        if i[0]<j[0] and i[1]<j[1]:
            count+=1
            del blue[n]
            break
print(count)

Submission status: Accepted

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

def main():
    N = int(input())
    pa = []
    for i in range(N):
        s = input().split()
        a, b = int(s[0]), int(s[1])
        pa.append((0, a, b))
    for i in range(N):
        s = input().split()
        c, d = int(s[0]), int(s[1])
        pa.append((1, c, d))

    pa.sort(key = lambda v: v[1])

    c = 0
    st = []
    for v in pa:
        if v[0] == 0:
            if len(st) == 0 or st[-1][2] > v[2]:
                st.append(v)
            else:
                for i, w in enumerate(st):
                    if v[2] > w[2]:
                        st.insert(i, v)
                        break
        else:
            for i in range(len(st)):
                if v[2] > st[i][2]:
                    st.pop(i)
                    c += 1
                    break


    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
red=sorted([list(map(int,input().split())) for i in range(N)], key=lambda x:-1*x[1])
blue=sorted([list(map(int,input().split())) for i in range(N)])
red = sorted(red, key = lambda x:x[1] * -1)
count=0
for i in red:
    for n,j in enumerate(blue):
        if i[0]<j[0] and i[1]<j[1]:
            count+=1
            del blue[n]
            break
print(count)

Submission status: Accepted

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

ans = 0
blue.sort()

for i in range(N):
    index = -1
    red_y_max = -1
    for j in range(len(red)):
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
            if red_y_max < red[j][1]:
                index = j
                red_y_max = red[j][1]
    if index != -1:
        red.pop(index)
        ans += 1

print(ans)

Submission status: Accepted

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

count = 0
for i in range(n):
    for j in range(len(B)):
        if A[i][0] < B[j][0] and A[i][1] < B[j][1]:
            count += 1
            B.pop(j)
            break
        
print(count)

Submission status: Accepted

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

for i in range(n):
    for j in range(len(sortCD)):
        if sortAB[i][0] < sortCD[j][0] and sortAB[i][1] < sortCD[j][1]:
            sortCD.pop(j)
            break
            
print(n - len(sortCD))

Submission status: Accepted

Solution code:
n = int(input())

AB = [[int(i) for i in input().split()] for i in range(n)]
CD = [[int(i) for i in input().split()] for i in range(n)]

AB = sorted(AB, reverse=True, key=lambda x: x[1])
CD = sorted(CD)

for i in range(n):
    for j in range(len(CD)):
        if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
            CD.pop(j)
            break
            
print(n - len(CD))

Submission status: Accepted

Solution code:
N = int(input())
reds = [tuple(map(int, input().strip().split())) for _ in range(N)]
blues = [tuple(map(int, input().strip().split())) for _ in range(N)]
redset = set()
for b in sorted(blues, key=lambda x: x[0]):
  for r in sorted(reds, key=lambda x: -x[1]):
    if r not in redset and b[0] > r[0] and b[1] > r[1]:
      redset.add(r)
      break
print(len(redset))

Submission status: Accepted

Solution code:
N = int(input())
Blue = []
Red = []
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 = sorted(Blue)
Red = list(reversed(sorted(Red,key=lambda x: x[1])))

ans = 0
for i in range(N) :
    for j in range(N) :
        if j >= len(Red) :
            break
        if (Blue[i][0] > Red[j][0]) and (Blue[i][1] > Red[j][1]) :
            ans += 1
            Red.pop(j)
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = []
B = []

for i in range(N):
    a,b = list(map(int, input().split()))
    R.append([a, b])

for i in range(N):
    c, d = list(map(int, input().split()))
    B.append([c,d])

B.sort()

pair = [0] * N
ans = 0

for i in range(N):
    bx, by = B[i]
    d = -1
    d_j = -1
    for j in range(N):
        ax, ay = R[j]
        if ax < bx and ay < by and pair[j] == 0:
            if ay > d:
                d = ay
                d_j = j
    if d_j != -1:
        pair[d_j] = 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())

R = []
for i in range(N):
    a, b = [int(x) for x in input().split()]
    R.append((a, b))

B = []
for i in range(N):
    c, d = [int(x) for x in input().split()]
    B.append((c, d))

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

ans = 0
used_idx = []
for b in B:
    idx = -1
    for i, r in enumerate(R):
        if b[0] > r[0] and b[1] > r[1]:
            if used_idx.count(i) == 0:
                idx = i
                break
    if idx != -1:
        used_idx.append(idx)
        ans += 1
        # print("{},{}".format(b, ma_r))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
pairs_ab = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[1], reverse=True) # red
pairs_cd = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[0]) # blue

cnt = 0
for pair_b in pairs_cd:
  for pair_a in pairs_ab:
    if pair_b[1] > pair_a[1] and pair_b[0] > pair_a[0]:
      cnt += 1
      pair_a[0] = pair_a[1] = float('inf')
      break

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

AB = [[int(i) for i in input().split()] for i in range(n)]
CD = [[int(i) for i in input().split()] for i in range(n)]

AB = sorted(AB, reverse=True)
CD = sorted(CD, key=lambda x: x[1])

for i in range(n):
    for j in range(len(CD)):
        if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
            CD.pop(j)
            break
            
print(n - len(CD))

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            key=lambda x: x[1],
            reverse=True)
CD = sorted([[int(_) for _ in input().split()] for _ in range(N)])
 
count = 0
for i in range(N):
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            del AB[j]
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            key=lambda x: x[1],
            reverse=True)
CD = sorted([[int(_) for _ in input().split()] for _ in range(N)])
 
for i in range(N):
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            del AB[j]
            break
print(N - len(AB))

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            key=lambda x: x[1],
            reverse=True)
CD = sorted([[int(_) for _ in input().split()] for _ in range(N)])
 
for i in range(N):
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            AB.pop(j)
            break
print(N - len(AB))

Submission status: Accepted

Solution code:
N = int(input())
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            key=lambda x: x[1],
            reverse=True)
CD = sorted([[int(_) for _ in input().split()] for _ in range(N)])
 
for i in range(N):
    p = -1
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            p = j
            break
    if p > -1:
        AB.pop(p)
print(N - len(AB))

Submission status: Accepted

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

for i in range(N):
    p = -1
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            p = j
            break
    if p > -1:
        AB.pop(p)
print(N - len(AB))

Submission status: Accepted

Solution code:
def print_arr(arr):
    for i in range(len(arr)):
        print(arr[i],sep=" ",end="")
    print()
    

from operator import itemgetter
n = int(input())
a=[]
b=[]
arr = [[0]*n for _ in range(n)]
for i in range(n):
    a.append(list(map(int,input().split())))
    a[-1].append(0)
for i in range(n):
    b.append(list(map(int,input().split())))
    b[-1].append(0)
b.sort(key=itemgetter(0))
a.sort(key=itemgetter(1))
a = a[::-1]
count = 0
for i in range(n):
    for j in range(n):
        if a[j][2] == 0 and b[i][2] == 0:
            if b[i][0] - a[j][0] > 0 and b[i][1] - a[j][1] > 0:
                count += 1
                a[j][2] = 1
                b[i][2] = 1
                continue
            
print(count)

Submission status: Accepted

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

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

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

count = 0
while len(blue) >= 1:
    c, d = blue.pop(0)
    tmp = []
    r = []
    while len(red) >= 1:
        a, b = red.pop()
        if a < c and b < d:
            r.append((a, b))
        else:
            tmp.append((a, b))
    if len(r) >= 1:
        count += 1
        r = sorted(r, key=lambda x:x[1])
        r.pop()
        tmp.extend(r)
    red.extend(tmp)
print(count)

Submission status: Accepted

Solution code:
n = (int)(input())

r = []
b = []

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

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

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

# print(r)
# print(b)
ans = 0
used_r = []
for i in range(n):
    #print("b", b[i])
    cnd = [v for v in r if v[0] < b[i][0]]
    cnd.sort(key=lambda x: x[1])
    pair = -1
    for j in range(len(cnd)):
        if cnd[j][1] < b[i][1]:
            pair = cnd[j]

    #print("cnd", cnd)
    #print("pair", pair)
    if pair != -1:
        r.remove(pair)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
r = []
b = []
c = 0
for i in range(n):
  r.append(list(map(int,input().split())))
for i in range(n):
  b.append(list(map(int,input().split())))
r.sort(key = itemgetter(1),reverse = True)
b.sort(key = itemgetter(0))
for i in range(n):
  for j in range(n):
    if b[i][0] > r[j][0] and b[i][1] > r[j][1]:
      r[j] = [10**6,10**6]
      c += 1
      break
print(c)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    reds = [list(map(int, input().split())) for _ in range(n)]
    blues = sorted(list(map(int, input().split())) for _ in range(n))
    res = 0
    for blue in blues:
        y_max = -1
        y_max_i = None
        for i, red in enumerate(reds):
            if red[0] > blue[0] or red[1] > blue[1]:
                continue
            if red[1] > y_max:
                y_max = red[1]
                y_max_i = i
        if y_max_i is not None:
            res += 1
            del reds[y_max_i]
    print(res)


if __name__ == '__main__':
    main()

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

n=int(input())
edges = [set() for _ in range(n)]
matched = [-1] * n
a=[]
b=[]
c=[]
d=[]
for _ in range(n):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)
for _ in range(n):
  x, y = map(int, input().split())
  c.append(x)
  d.append(y)
for i in range(n):
  for j in range(n):
    if(a[i]<c[j] and b[i]<d[j]):
      edges[i].add(j)
print(sum(dfs(s, set()) for s in range(n)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "r"))
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "b"))
    points.sort(lambda x: x[0])
    singles = []
    retval = 0
    for p in points:
        x, y, c = p
        if c == "r":
            singles.append(y)
        if c == "b":
            maximum = (-1, -1)
            for i, v in enumerate(singles):
                if v < y and v > maximum[1]:
                    maximum = (i, v)
            if maximum[0] != -1:
                retval += 1
                singles.pop(maximum[0])
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
red = []
for i in range(n):
    red.append(list(map(int, input().split())))
blue = []
for i in range(n):
    blue.append(list(map(int, input().split())))
red_sort = sorted(red, key=lambda x: x[1], reverse=True)
blue_sort = sorted(blue)
count = 0
flag = [0]*n
for b in blue_sort:
    for i,r in enumerate(red_sort):
        if r[0] < b[0] and r[1] < b[1] and flag[i] == 0:
            count += 1
            flag[i] = 1
            break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
red = []
for i in range(n):
    red.append(list(map(int, input().split())))
blue = []
for i in range(n):
    blue.append(list(map(int, input().split())))
red_sort = sorted(red, key=lambda x: x[1], reverse=True)
blue_sort = sorted(blue)
count = 0
flag = [0] * n
for b in blue_sort:
    for i, r in enumerate(red_sort):
        if r[0] < b[0] and r[1] < b[1] and flag[i] == 0:
            count += 1
            flag[i] = 1
            break
print(count)

Submission status: Accepted

Solution code:
N = int(input())
red_list = [list(map(int, input().split())) for i in range(N)]
blue_list = [list(map(int, input().split())) for i in range(N)]
ans = 0

def x_axis_evaluate(li):
    return li[0]

def y_axis_evaluate(li):
    return li[1]

red_list.sort(key=y_axis_evaluate,reverse=True)
blue_list.sort(key=x_axis_evaluate)

for b_item in blue_list:
    for r_item in red_list:
        if r_item[0] < b_item[0] and r_item[1] < b_item[1]:
            ans += 1
            red_list.remove(r_item)
            break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

R=[]
for i in range(N):
    a,b=map(int,input().split())
    R.append([a,b])
R.sort()
    
B=[]
for j in range(N):
    c,d=map(int,input().split())
    B.append([c,d])
B.sort()

cnt=0
K=[]
for x in range(N):
    for y in range(N):
        if B[x][0]>R[y][0] and B[x][1]>R[y][1]:
            K.append([R[y][1],R[y][0],y])
    if K==[]:
        pass
    else:
        K.sort(reverse=True)
        R[K[0][2]]=[1000,1000]
        cnt+=1
        K=[]
print(cnt)

Submission status: Accepted

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

import operator
R.sort(key=operator.itemgetter(1),reverse=True)
B.sort()

ans=0
for b in B:
    xb,yb=b
    for r in R:
        xr,yr=r
        if xr<xb and yr<yb:
            ans+=1
            R.remove(r)
            break
print(ans)

Submission status: Accepted

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

bs.sort()

#lambdaを使ってy座標でソート
#list.sort(key=lambda x:x[i])でi番目の要素によるソート
#lambda x : -x[1]とすることでrsを降順にできる
rs.sort(key=lambda x: -x[1])

ans = 0
for bx, by in bs:
    for rx, ry in rs:
        if rx < bx and ry < by:
            rs.remove((rx, ry))
            ans += 1
            break
        else:
            continue
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

R = [list(map(int, input().split())) for i in range(N)]
B = [list(map(int, input().split())) for i in range(N)]
R.sort(key = lambda x:x[1], reverse = True)
B.sort()
ans = 0
check = []


for bx, by in B:
    for i in range(N):
        if bx > R[i][0] and by > R[i][1] and i not in check :
            ans += 1
            check.append(i)
            break
            #print('B', bx, by, 'R',R[i][0], R[i][1] )
print(ans)

Submission status: Accepted

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

import operator
R.sort(key=operator.itemgetter(1), reverse=True)
B.sort()

ans = 0
for b in B:
    xb, yb = b
    for r in R:
        xr, yr = r
        if xr < xb and yr < yb:
            ans += 1
            R.remove(r)
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = [[] for i in range(N)]
B = [[] for i in range(N)]
for i in range(N):
  R[i] = [int(x) for x in input().split()]
for i in range(N):
  B[i] = [int(x) for x in input().split()]
B.sort()
cnt = 0
for i in range(N):
  pair = [N, -1]
  for j in range(N):
    if R[j][0] < B[i][0] and R[j][1] < B[i][1]:
      if R[j][1] > pair[1]:
        pair = [j, R[j][1]]
  if pair[0] < N:
    cnt += 1
    R[pair[0]][1] = 2 * N
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
iN = int(input())
#aR = [(i,[int(_) for _ in input().split()]) for i in range(iN)]
#aB = [(i,[int(_) for _ in input().split()]) for i in range(iN)]
aR = sorted([[int(_) for _ in input().split()] for i in range(iN)],key=lambda x:x[1])
aB = sorted([[int(_) for _ in input().split()] for i in range(iN)])

dDicided = set()
for bx,by in aB:
    dCand = []
    for i,[rx,ry] in enumerate(aR):
        if i in dDicided:
            continue
        if bx > rx and by > ry:
            dCand.append([ry,i])
    if dCand != []:
        dDicided.add(sorted(dCand ,reverse=True)[0][1])

print(len(dDicided))

Submission status: Accepted

Solution code:
n=int(input())
data=[]


for i in range(n):
    tmp=[0]*3
    tmp[0],tmp[1]=map(int,input().split())
    data.append(tmp)

for i in range(n):
    tmp=[1]*3
    tmp[0],tmp[1]=map(int,input().split())
    data.append(tmp)    

data.sort(key=lambda x:x[0])

ans=0
j=2*n-1
while(data[j][2]==0):
    j-=1

ttmp=[]
while(1):
    tmp=[data[j]]
    while(1):
        j-=1
        if(j==-1):
            break
        tmp.append(data[j])
        if(data[j][2]==0):
            break
    while(1):
        j-=1
        if(j<=-1):
            break
        if(data[j][2]==1):
            break
        else:
            tmp.append(data[j])
    ttmp+=tmp
    ttmp.sort(key=lambda x:x[1])
    red=0

    tttmp=[ttmp[i] for i in range(len(ttmp))]
    delnum=0
    for i in range(len(tttmp)):
        if(tttmp[i][2]==0):
            red+=1
            ttmp.pop(i-delnum)
            delnum+=1
        else:
            if(red>=1):
                ans+=1
                red-=1
                ttmp.pop(i-delnum)
                delnum+=1
    if(j<=-1):
        break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
rs = [list(map(int, input().split())) for _ in range(n)]
bs = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
flgs = [False for _ in range(n)]

ans = 0
for b in bs:
    bx, by = b
    ty = -1
    tid = -1
    for j in range(n):
        rx, ry = rs[j]
        if flgs[j]: continue
        if bx > rx and by > ry:
            if ty < ry:
                ty = ry
                tid = j
    if tid != -1:
        flgs[tid] = True
        ans += 1

print(ans)