【AtCoder版！蟻本】ABC038 D - プレゼント【区間スケジューリング】

AtCoder版！蟻本の区間スケジューリングの例題としてあげられているABC038 D - プレゼントをPythonで解いていきます。

リンク

D - プレゼント

ABC038 D - プレゼント

問題文

高橋くんはプレゼントを用意することになりました。プレゼントの中身はすでに決まり、あとはプレゼントを入れる箱を用意するだけです。 高橋くんが使える箱はN個あり、i番目の箱は縦hi cm×横wi cmのサイズです。

プレゼントがより多くの箱に入っていたほうが面白いと考えた高橋くんは、なるべく多くの箱を入れ子にし、最も内側の箱にプレゼントを入れることにしました。 ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができます。また、ある箱は1つまでしか他の箱を入れることはできません。

プレゼントを入れる箱を最大で何重の入れ子にできるか答えてください。

制約

・1≦N≦10^5
・1≦hi≦10^5
・1≦wi≦10^5

解答例

n = int(input())

Size = []
for i in range(n):
    w, h = map(int, input().split())
    Size.append([w, h])

Size.sort()
Size.sort(key= lambda x:x[1])
 
width = Size[0][0]
depth = Size[0][1]

ans = 1

for i in range(n):
    if width < Size[i][0] and depth < Size[i][1]:
        width = Size[i][0]
        depth = Size[i][1]
        ans += 1

print(ans)

解説

縦横の長さが決まっているN個の箱があり、縦横ともに小さい箱があれば入れ子にすることができます。
最大で何重の入れ子にできるか答える問題です。

箱のサイズをSize配列で受け取り、縦と横についてソートします。

ソート済みとなったので、配列の最初の要素を横と縦の初期条件width・depthとしました。

ループでN個の箱を調べていき、現在の箱よりwidthとdepthがともに大きい箱があったときansに1を足していきます。
同時にwidthとdepthを更新します。

このループを抜けることで入れ子の最大値がansに格納されますので、出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク