ARC092 C – 2D Plane 2N Points｜かえるのほんだな

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ARC092 C – 2D Plane 2N Pointsを解きました。

難易度は水色。

考察

赤玉も青玉も、xでソートしておく。

ある一つの青玉を基準に考えたとき、その青玉とペアになれるのは、xとyの値が青玉未満の赤玉である。

この範囲の中で、xが青玉未満かつ、yが青玉未満の赤玉の中から、最もyの値が「大きい」ものを貪欲的に選択していく。

コード

N = int(input())

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

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

R.sort()
B.sort()
ans1 = 0
for i in range(N):
    bx = B[i][0]
    by = B[i][1]

    max_j = -1
    max_y = -1
    for j in range(N):
        rx = R[j][0]
        ry = R[j][1]
        if R[j][2]:
            continue

        if rx > bx:
            break

        if rx < bx and ry < by:
            if ry >= max_y:
                max_y = ry
                max_j = j

    if max_j != -1:
        R[max_j][2] = True
        ans1 += 1

print(ans1)