โปรแกรมหาความสูงอาคารสูงสุดภายใต้ข้อจำกัดใน Python

ปัญหา

สร้างอาคาร n หลังเรียงต่อกัน (1 ถึง n) ข้อจำกัด: ความสูง ≥ 0, อาคารแรกสูง 0, ความต่างระหว่างอาคารติดกัน ≤ 1 มี Restrictions: (id_i, max_height_i) บังคับอาคาร id_i ต้องสูง ≤ max_height_i หาความสูงสูงสุดที่เป็นไปได้ของอาคารที่สูงที่สุด

ตัวอย่าง

n = 5, restrictions = [[2,1],[4,3]] → Output: 4

ความสูงที่เป็นไปได้: [0, 1, 2, 3, 4] (อาคารที่ 5 สูง 4)

อัลกอริทึม (Two Pass + Peak Calculation)

1. เรียง Restrictions ตาม ID
2. Forward Pass: ปรับ max_height ให้สอดคล้องกับข้อจำกัด "ความต่าง ≤ 1" จากซ้ายไปขวา
3. Backward Pass: ปรับ max_height จากขวาไปซ้าย
4. คำนวณ Peak สูงสุดระหว่าง Restrictions แต่ละคู่: (dist + h1 + h2) // 2
5. พิจารณาส่วนท้ายหลัง Restriction สุดท้าย

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

def solve(n, restrictions):
    if not restrictions:
        return n - 1
    
    resi = sorted(restrictions, key=lambda x: x[0])
    k, idx = 0, 1
    
    # Forward pass
    for re in resi:
        re[1] = min(re[1], k + re[0] - idx)
        k = re[1]
        idx = re[0]
    
    # Backward pass
    k = resi[-1][1]
    idx = resi[-1][0]
    resi.reverse()
    for re in resi[1:]:
        re[1] = min(re[1], k - re[0] + idx)
        k = re[1]
        idx = re[0]
    resi.reverse()
    
    # Calculate max peak
    f, idx, res = 0, 1, 0
    for re in resi:
        ff = min(f + re[0] - idx, re[1])
        res = max(res, (re[0] - idx + f + ff) // 2)
        idx = re[0]
        f = ff
    
    return max(f + n - idx, res)

n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))  # 4

ความซับซ้อน

• Time: O(r log r) โดย r = จำนวน Restrictions
• Space: O(r)