สมมติว่าเรามีรายการช่วงเวลาสำหรับการฉายภาพยนตร์ต่างๆ (สามารถซ้อนทับกันได้) เราต้องหาจำนวนโรงภาพยนตร์ขั้นต่ำที่จำเป็นในการฉายภาพยนตร์ทั้งหมด
ดังนั้น หากอินพุตเหมือนช่วงเวลา =[[20, 65],[0, 40],[50, 140]] ผลลัพธ์จะเป็น 2 เนื่องจาก [20, 65] และ [0, 40] ทับซ้อนกัน . [20, 65] และ [50, 140] ก็ทับซ้อนกันเช่นกัน แต่ [0, 40] และ [50, 140] ไม่ทับซ้อนกัน เลยต้องมีโรงหนัง 2 โรง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- t :=รายการใหม่
- สำหรับแต่ละช่วง [a, b] ในช่วงเวลา ให้ทำ
- ใส่ [a, 1] ต่อท้าย t
- ใส่ [b, -1] ต่อท้าย t
- ตอบ :=0, นับ :=0
- สำหรับแต่ละคู่ (x, d) ใน t ในรูปแบบการเรียงลำดับ ทำ
- นับ :=นับ + d
- ans :=จำนวน 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
