"プレゼント" AtCoder Beginner Contest 038 D

D - プレゼント

解法
最長増加部分列(LIS)の問題として解きました。
実装は蟻本の63~65ページを参考にしています。
まずは箱の幅で昇順にソート、幅が同じ箱どうしでは高さの降順にソートします。
そして高さのみを考えてLISを求めれば答えが出ます。
dp[i]は、「長さがi+1であるような増加部分列における最終要素の最小値」で、dpは最初全部の要素が114514。
heightを前から見ていき、二分探索でheight[k]をdpのどこに挿入できるかを探してdpを更新していく。
これを最後までやると、箱をi+1重にできる場合はdp[i]が114514より小さくなっているので答えがわかる。

# ABC038D
import bisect
N = int(input())
hako = []

for k in range(N):
    hako.append(list(map(int, input().split())))

hako = sorted(hako, key = lambda x: (x[0],-x[1]))
height = []
for k in range(N):
    height.append(hako[k][1])

dp = [114514] * (N+1)
for k in range(N):
    dp[bisect.bisect_left(dp, height[k])] = height[k]

ans = 0
for k in range(N+1):
    if dp[k] < 114514:
        ans = k+1
print(ans)