โปรแกรมหาจำนวนเซลล์ที่มีค่าสูงสุดในเมทริกซ์หลังการอัปเดตใน Python

มีเมทริกซ์ n x n เริ่มต้นเป็น 0 ได้รับลิสต์คู่ (row, col) สำหรับแต่ละคู่ ให้เพิ่ม 1 ให้ทุกเซลล์ที่แถว < row และคอลัมน์ < col หลังจบ ต้องการจำนวนเซลล์ที่มีค่าสูงสุด

ตัวอย่าง: input_list=[[3,5],[4,6],[5,3]] → ผลลัพธ์ 9

ขั้นตอนการแก้ปัญหา

สังเกตว่าเซลล์ที่ได้รับการเพิ่มมากที่สุดคือพื้นที่สี่เหลี่ยมจาก (0,0) ถึง (min_row, min_col) โดย min_row และ min_col คือค่าต่ำสุดของ row และ col ในลิสต์

1. หา xpos = min(item[0] for item in input_list)
2. หา ypos = min(item[1] for item in input_list)
3. คืนค่า xpos * ypos

ตัวอย่างโค้ด Python

def solve(input_list):
    xpos = 0
    ypos = 0
    for item in input_list:
        if xpos == 0:
            xpos = item[0]
            ypos = item[1]
        else:
            xpos = min(xpos, item[0])
            ypos = min(ypos, item[1])
    return xpos * ypos

# ทดสอบ
print(solve([[3, 5], [4, 6], [5, 3]]))  # ผลลัพธ์: 9

อินพุตตัวอย่าง

[[3, 5], [4, 6], [5, 3]]

เอาต์พุตตัวอย่าง

9