โปรแกรมตรวจสอบว่ารถรับส่งผู้โดยสารได้ครบทุกคนหรือไม่ (Python)

ปัญหา

กำหนด trips = [[start_x, end_x, num_passengers], ...] และ capacity ของรถ
รถเริ่มที่ x=0 เคลื่อนที่ไปทางขวาเท่านั้น ต้องรับ-ส่งผู้โดยสารครบทุกการเดินทาง ตรวจสอบว่า capacity พอหรือไม่

ตัวอย่าง: trips=[[1,25,2],[3,4,3],[5,12,3]], capacity=6 → True

วิธีแก้: Sweep Line Algorithm (Event-based)

แปลงแต่ละ trip เป็น 2 events: รับ (+passengers) ที่ start, ส่ง (-passengers) ที่ end
เรียง events ตามตำแหน่ง แล้วสะสมจำนวนผู้โดยสารตรวจสอบทุกจุด

อัลกอริทึม

1. สร้าง events list: (position, delta_passengers)
2. เรียง events ตาม position
3. วนลูปสะสม carrying += delta
4. ถ้า carrying > capacity ที่จุดไหน → False
5. จบลูป → True

โค้ด Python

class Solution:
    def solve(self, trips, capacity):
        events = []
        for sx, ex, np in trips:
            events.append((sx, np))    # รับผู้โดยสาร
            events.append((ex, -np))   # ส่งผู้โดยสาร
        
        carrying = 0
        for loc, delta in sorted(events):
            carrying += delta
            if carrying > capacity:
                return False
        return True

# ทดสอบ
ob = Solution()
trips = [[1, 25, 2], [3, 4, 3], [5, 12, 3]]
capacity = 6
print(ob.solve(trips, capacity))  # True

# ทดสอบ False case
trips2 = [[1, 5, 4], [2, 6, 3]]
print(ob.solve(trips2, 5))  # False (ที่ x=2 มี 7 คน > 5)

ความซับซ้อน

• Time: O(n log n) - เรียง 2n events
• Space: O(n) - เก็บ events

การทำงานตัวอย่าง

Events: (1,+2), (3,+3), (4,-3), (5,+3), (12,-3), (25,-2)
Sorted: (1,+2)→2, (3,+3)→5, (4,-3)→2, (5,+3)→5, (12,-3)→2, (25,-2)→0
Max carrying = 5 ≤ 6 → True

ประยุกต์ใช้

Meeting rooms, CPU scheduling, resource allocation, interval overlapping problems