[プログラマー]8週目最小矩形

最小長方形
問題の説明
名刺入れを作っている会社は財布の大きさを確認したいです.様々な形や大きさの名刺を収納でき、コンパクトで持ち運びに便利な財布を作る必要があります.これらの要件を満たすために、設計チームはすべての名刺の横方向と縦方向の長さを調査した.
次の表に、4種類の名刺の水平と垂直の長さを示します.
名刺番号横長縦長
1 60 50
2 30 70
3 60 30
4 80 40
最も長い横長と縦長はそれぞれ80と70であるため、80(横)x 70(縦)サイズの財布を作成すると、すべての名刺を収容することができる.ただし、横に2番の名刺を収納する場合は、80(横)x 50(縦)サイズの財布ですべての名刺を収納できます.財布のサイズは4000(=80 x 50)です.
パラメータは、すべての名刺の水平と垂直の長さを表す2 D配列サイズです.すべての名刺を収納できる最小財布を作成する場合は、財布の大きさを返すための解関数を完了します.
せいげんじょうけん
sizesの長さは10000より大きい.
sizesの要素は[w,h]形式です.
w名刺の水平長さを表す.
hは名刺の垂直な長さを表す.
wとhは1以上1000以下の自然数である.
I/O例
sizes result
[[60, 50], [30, 70], [60, 30], [80, 40]] 4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133
I/O例説明
I/O例#1
問題の例を以下に示します.
I/O例#2
名刺を適当に回して重ねると、3枚目の名刺(横:8、縦:15)が他のすべての名刺よりも大きくなります.そのため、財布の大きさは3枚目の名刺の大きさと同じで、120(=8 x 15)を返します.
I/O例#3
名刺が適切に回転して重なると、すべての名刺を含む最小財布サイズは133(=19 x 7)となる.

📋 に答える

入力されたすべての名刺(指定されたリストの最大値を出力)を含めることができますが、その値は最小でなければなりません.名刺を回して財布に入れることができるので、取り外しやすいようにドアをもっと高い値段に固定するのが条件です.

def solution(sizes):
    width = 1
    height = 1
    
    for size in sizes:
        max_size = max(size)
        min_size = min(size)
        
        if max_size >= width:
            width = max_size
        if min_size >= height:
            height = min_size
    
    return width * height

min関数とmax関数の時間複雑度はO(n)であるであるため,以上のコードの時間的複雑度はO(n 2)である.時間の複雑さを減らすために,コードを修正した.

def solution(sizes):
    width = 1
    height = 1
    
    for now_width, now_height in sizes:
        if now_height > now_width:
            now_width, now_height = now_height, now_width
        
        if now_width >= width:
            width = now_width
        if now_height >= height:
            height = now_height
    
    return width * height

どうせ縦横の長さを入力しているので、リストごとに2つの値しかなく、O(n)でも運転時間に大きな差はないと思います.すべての値を巡回した後、実際にはどの値がより大きく、より小さいかを判断するプロセスが含まれているため、値が大きいほど実行時間が長くなります.