โปรแกรมหาจำนวนโรงหนังขั้นต่ำสำหรับแสดงภาพยนตร์ทั้งหมดใน Python

สมมติว่ามีรายการช่วงเวลา (intervals) ของการฉายหนัง (อาจทับซ้อนกัน) ต้องการหาจำนวนโรงหนังขั้นต่ำที่จำเป็นเพื่อฉายหนังทั้งหมด

ตัวอย่าง: intervals = [[20, 65], [0, 40], [50, 140]] ผลลัพธ์คือ 2 เพราะ [20, 65] ทับกับ [0, 40] และ [50, 140] แต่ [0, 40] กับ [50, 140] ไม่ทับกัน

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

1. สร้างรายการ t ว่าง
2. แต่ละ interval [a, b] เพิ่ม [a, 1] (เริ่ม) และ [b, -1] (จบ) เข้า t
3. ans = 0, count = 0
4. เรียง t แล้ววนลูปแต่ละ (x, d):
   • count += d
   • ans = max(ans, count)
5. คืนค่า ans

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

class Solution:
    def solve(self, intervals):
        t = []
        for a, b in intervals:
            t.append((a, 1))
            t.append((b, -1))
        ans = count = 0
        for x, d in sorted(t):
            count += d
            ans = max(ans, count)
        return ans

ob = Solution()
intervals = [[20, 65], [0, 40], [50, 140]]
print(ob.solve(intervals))

อินพุต

[[20, 65], [0, 40], [50, 140]]

เอาต์พุต

2