ปัญหาการรับส่งผู้โดยสารรถยนต์ (Car Pooling) ใน Python

โจทย์: รถตู้มีที่นั่งว่าง capacity ขับไปทางตะวันออกเท่านั้น กำหนดรายการเที่ยวเดินทาง trips[i] = [num_passengers, start, end] ตรวจสอบว่าสามารถรับ-ส่งผู้โดยสารทุกคนได้หรือไม่โดยไม่เกินความจุ

ตัวอย่าง

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: True

อัลกอริทึม: Sweep Line / Difference Array

1. สร้างอาร์เรย์ stops ขนาด 1001 (constraint สูงสุด) เติม 0
2. สำหรับแต่ละ trip: stops[start] += passengers, stops[end] -= passengers
3. วิ่ง prefix sum ตาม stops ตรวจสอบว่า capacity ไม่ติดลบ

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

class Solution(object):
    def carPooling(self, trips, capacity):
        stops = [0] * 1001  # constraint: location <= 1000
        
        # มาร์กการขึ้น-ลง
        for trip in trips:
            stops[trip[1]] += trip[0]   # ขึ้นที่ start
            stops[trip[2]] -= trip[0]   # ลงที่ end
        
        # ตรวจสอบความจุตลอดเส้นทาง
        for change in stops:
            capacity -= change
            if capacity < 0:
                return False
        
        return True

# ทดสอบ
ob = Solution()
print(ob.carPooling([[2,1,5],[3,3,7]], 5))  # Output: True

ตัวอย่าง Input/Output

Input: [[2,1,5],[3,3,7]] 5
Output: True

ความซับซ้อน: Time O(n + max_location), Space O(max_location) - มีประสิทธิภาพสูงสำหรับ constraint ปกติ